fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. #define ll long long
  6. #define fi first
  7. #define se second
  8. #define pb push_back
  9. #define C make_pair
  10. #define FOR(i, a, b) for(int i = (a), _b = (b); i <= _b; i++)
  11. #define FORD(i, b, a) for(int i = (b), _a = (a); i >= _a; i--)
  12. #define REP(i, n) for(int i = 0, _n = (n); i < _n; i++)
  13. #define MASK(i) (1LL << (i))
  14. #define BIT(i, x) ((x) & MASK(i))
  15. #define TURN_ON(i, x) ((x) | MASK(i))
  16. #define TURN_OFF(i, x) ((x) & ~MASK(i))
  17. #define REV(i, x) ((x) ^ MASK(i))
  18.  
  19. template<typename T>bool maximize(T &res, const T &a){if(res < a) return res = a, true; return false;}
  20. template<typename T>bool minimize(T &res, const T &a){if(res > a) return res = a, true; return false;}
  21.  
  22. const int maxn = (int)1e5 + 5;
  23. const ll MOD = 1e9 + 7;
  24. const ll INF = 1e15;
  25.  
  26. typedef pair<int, int> pi;
  27. typedef pair<int, pi> pii;
  28. typedef pair<ll, ll> pl;
  29. typedef pair<ll, pl> pll;
  30.  
  31. int n, m, low[2 * maxn], num[2 * maxn], cnt, bridge;
  32. pi edge[10 * maxn];
  33. bool check[10 * maxn];
  34. vector<int>a[2 * maxn];
  35.  
  36. void dfs(int u){
  37. 	num[u] = low[u] = ++cnt;
  38.  
  39. 	for(int id: a[u]) if(!check[id]){
  40. 		check[id] = 1;
  41. 		int v = edge[id].fi + edge[id].se - u;
  42. 		if(num[v]) minimize(low[u], num[v]);
  43. 		else{
  44. 			dfs(v);
  45. 			minimize(low[u], low[v]);
  46. 			if(low[v] > num[u]) bridge++;
  47. 		}
  48. 	}
  49. }
  50. void nhap(){
  51. 	cin >> n;
  52. 	FOR(i, 1, n - 1){
  53. 		int u, v; cin >> u >> v;
  54. 		a[u].pb(i);
  55. 		a[v].pb(i);
  56. 		edge[i] = C(u, v);
  57. 	}
  58. 	cin >> m;
  59. 	FOR(i, 1, m){
  60. 		int u, v; cin >> u >> v;
  61. 		a[u].pb(i + n);
  62. 		a[v].pb(i + n);
  63. 		edge[i + n] = C(u, v);
  64. 	}
  65. }
  66. void solve(){
  67. 	dfs(1);
  68. 	cout << bridge;
  69. }
  70. int main() {
  71. 	ios_base::sync_with_stdio(0);
  72. 	cin.tie(0); cout.tie(0);
  73. 	nhap();
  74. 	solve();
  75. 	return 0;
  76. }
Success #stdin #stdout 0.01s 11000KB
comments (?)
stdin
copy 
6
1 2
2 3
2 4
4 5
4 6
2
3 6
5 6
stdout
copy 
1
https://ideone.com/ix9vqr
language:
C++14 (gcc 8.3)
created:
1 day ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!