fork download
copy 
  1. #include <bits/stdc++.h> 
  2.  
  3. using namespace std;  
  4.  
  5. typedef long long ll;  
  6. typedef pair<int, int> ii;  
  7.  
  8. const int INF = 1e9;  
  9. const ll LINF = 1e18;  
  10.  
  11. const int N = 2e5 + 5; 
  12.  
  13. // Ta có tính chất sau của cây: tất cả các cạnh của cây đều là cạnh cầu
  14. // Nhận xét: 
  15. // Khi ta thêm một cạnh (u, v) vào cây thì chắc chắn sẽ tạo chu trình, 
  16. // chu trình này sẽ chứa hết tất cả các cạnh trên đường đi từ u đến v ở trên cây
  17. // Dẫn đến các cạnh này không còn là cạnh cầu nữa
  18.  
  19. // Từ đây với mỗi truy vấn cần đánh dấu các cạnh nằm trên đường đi từ u đến v
  20. // thì ta sẽ thêm cạnh (u, v) vào đồ thị
  21. // Sau toàn bộ truy vấn, những cạnh cầu có trong đồ thị sẽ là những cạnh mà chưa được đánh dấu
  22. // Lưu ý đồ thị lúc này có thể là đa đồ thị (giữa 2 đỉnh bất kì có thể có nhiều cạnh nối)
  23. int n; 
  24. int m;   
  25. vector<int> adj[N];
  26.  
  27. int tin[N], low[N], timer;  
  28. int cnt_bridge; 
  29.  
  30. void dfs(int u, int p) {
  31. 	tin[u] = low[u] = ++timer; 
  32.  
  33. 	bool parent_skipped = true;  
  34. 	for (int v : adj[u]) {
  35. 		if (v == p && parent_skipped) {
  36. 			parent_skipped = false;
  37. 			continue;
  38. 		}
  39.  
  40. 		if (!tin[v]) {
  41. 			dfs(v, u);
  42. 			low[u] = min(low[u], low[v]);
  43. 			if (low[v] > tin[u]) cnt_bridge++;
  44. 		}
  45. 		else {
  46. 			low[u] = min(low[u], tin[v]);
  47. 		}
  48. 	}
  49. }
  50.  
  51. int main() {
  52. 	ios::sync_with_stdio(false); 
  53. 	cin.tie(nullptr); 	
  54. 	cin >> n;
  55. 	for (int i = 0; i < n - 1; i++) {
  56. 		int u, v; 
  57. 		cin >> u >> v; 
  58. 		adj[u].push_back(v);
  59. 		adj[v].push_back(u); 
  60. 	}
  61.  
  62. 	cin >> m; 
  63. 	for (int i = 0; i < m; i++) {
  64. 		int u, v; 
  65. 		cin >> u >> v; 
  66. 		adj[u].push_back(v); 
  67. 		adj[v].push_back(u); 
  68. 	}
  69.  
  70. 	timer = 0;   
  71. 	cnt_bridge = 0;   
  72. 	dfs(1, -1); 
  73.  
  74. 	cout << cnt_bridge << '\n'; 
  75. }
Success #stdin #stdout 0.01s 8284KB
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/itqcnQ
language:
C++14 (gcc 8.3)
created:
275 days ago
visibility:
secret

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!