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 = 1e5 + 5; 
  12.  
  13. int n, m, q; 
  14. vector<int> adj[N]; 
  15.  
  16. int tin[N]; // tin[u] = thời gian dfs đi vào đỉnh u 
  17. int tout[N]; // tout[u] = thời gian dfs đi ra khỏi đỉnh u 
  18. int low[N], timer;   
  19. vector<int> child[N]; // child[u]: danh sách các đỉnh là con của u trên cây dfs, được sort tăng dần theo giá trị tin[]
  20. bool is_cutpoint[N]; // is_cutpoint[u] = true/false: u có phải là đỉnh khớp hay không
  21.  
  22. void dfs(int u, int p) {
  23. 	tin[u] = low[u] = ++timer; 
  24.  
  25. 	for (int v : adj[u]) {
  26. 		if (v == p) continue; 
  27. 		if (!tin[v]) {
  28. 			child[u].push_back(v); 
  29. 			dfs(v, u); 
  30. 			low[u] = min(low[u], low[v]);  
  31. 			if (low[v] >= tin[u] && p != -1) is_cutpoint[u] = true; 
  32. 		}
  33. 		else {
  34. 			low[u] = min(low[u], tin[v]);
  35. 		}
  36. 	}
  37.  
  38. 	if (p == -1) {
  39. 		is_cutpoint[u] = (child[u].size() >= 2); 
  40. 	}
  41.  
  42. 	tout[u] = ++timer;  
  43. }
  44.  
  45. // Kiểm tra u có phải là tổ tiên của v hay không
  46. bool isAncestor(int u, int v) {
  47. 	return (tin[u] <= tin[v] && tin[v] <= tout[u]); 
  48. }
  49.  
  50. // Trả lời truy vấn loại 1
  51. bool solve1(int a, int b, int g1, int g2) {
  52. 	// Không mất tính tổng quát, giả sử g1 là cha của g2
  53. 	if (tin[g1] > tin[g2]) swap(g1, g2); 
  54.  
  55. 	// Nếu cạnh (g1, g2) không phải là cầu thì kết quả auto là yes
  56. 	if (low[g2] != tin[g2]) return true;  
  57.  
  58. 	// Nếu cạnh (g1, g2) là cầu thì a, b phải cùng thuộc một thành phần liên thông sau khi xoá cạnh (g1, g2)
  59. 	// tức a, b phải đều thuộc cây con gốc g2 hoặc đều nằm ngoài cây con gốc g2
  60. 	// để kiểm tra cây con gốc y có chứa đỉnh x hay không thì ta kiểm tra y có phải tổ tiên của x hay không 
  61. 	if ((isAncestor(g2, a) && isAncestor(g2, b)) ||
  62. 		(!isAncestor(g2, a) && !isAncestor(g2, b))) 
  63. 		return true; 
  64.  
  65. 	return false; 
  66. }
  67.  
  68. // Tìm đỉnh v sao cho v là con của c và v là tổ tiên của u
  69. // Ta có nhận xét:
  70. // Một đỉnh v là tổ tiên của u nếu đoạn [tin[v], tout[v]] chứa tin[u]
  71. // Khi xét các đỉnh con v của c với thứ tự tăng dần theo tin
  72. // thì các đoạn [tin[v], tout[v]] sẽ xếp tăng dần và liên tiếp nhau (chứng minh thông qua quá trình dfs)
  73. // Nên ta có thể tìm nhanh đỉnh v thoả mãn bằng tìm kiếm nhị phân 
  74. int findP(int c, int u) {
  75. 	// Trường hợp u nằm ngoài cây con gốc c thì hiển nhiên không tồn tại đỉnh v cần tìm
  76. 	if (!isAncestor(c, u)) return -1;   
  77.  
  78. 	int l = 0, r = child[c].size() - 1, ans = -1; 
  79. 	while (l <= r) {
  80. 		int mid = (l + r) >> 1; 
  81. 		int cur = child[c][mid];  
  82. 		if (tin[cur] <= tin[u]) {
  83. 			ans = mid;  
  84. 			l = mid + 1; 
  85. 		}
  86. 		else {
  87. 			r = mid - 1; 
  88. 		}
  89. 	}
  90. 	return child[c][ans];
  91. }
  92.  
  93. // Trả lời truy vấn loại 2
  94. bool solve2(int a, int b, int c) {
  95. 	// Trường hợp c không phải là khớp thì kết quả auto là yes
  96. 	if (!is_cutpoint[c]) return true;  
  97.  
  98. 	// pa là con của c mà là tổ tiên của a
  99. 	// pb là con của c mà là tổ tiên của b
  100. 	// Sau đó ta chỉ cần xét qua một số trường hợp
  101. 	int pa = findP(c, a), pb = findP(c, b); 
  102. 	// a và b đều nằm ngoài cây con gốc c
  103. 	if (pa == -1 && pb == -1) {
  104. 		return true; 
  105. 	} 
  106.  
  107. 	// a nằm ngoài cây con gốc c, b nằm trong cây con gốc c
  108. 	// khi đó khi xoá c thì b phải có đường đi lên tổ tiên nào đấy của c
  109. 	if (pa == -1 && pb != -1) {
  110. 		if (low[pb] < tin[c]) return true;  
  111. 		return false;
  112. 	}
  113.  
  114. 	// a nằm trong cây con gốc c, b nằm ngoài cây con gốc c
  115. 	// tương tự trường hợp trên
  116. 	if (pa != -1 && pb == -1) {
  117. 		if (low[pa] < tin[c]) return true;  
  118. 		return false;
  119. 	}
  120.  
  121. 	// a và b cùng nằm trong cây con gốc c
  122. 	if (pa == pb) return true; // a, b cùng thuộc chung một nhánh 
  123. 	if (low[pa] < tin[c] && low[pb] < tin[c]) return true; // ngược lại khi xoá c 
  124. 														   // thì a, b đều phải có đường đi lên tổ tiên nào đấy của c
  125. 	return false;
  126. }
  127.  
  128. int main() {
  129. 	ios::sync_with_stdio(false); 
  130. 	cin.tie(nullptr); 	
  131. 	cin >> n >> m; 
  132. 	for (int i = 0; i < m; i++) {
  133. 		int u, v; 
  134. 		cin >> u >> v; 
  135. 		adj[u].push_back(v); 
  136. 		adj[v].push_back(u); 
  137. 	}
  138.  
  139. 	timer = 0;
  140. 	dfs(1, -1);  
  141.  
  142. 	cin >> q; 
  143.  
  144. 	while (q--) {
  145. 		int type, a, b; 
  146. 		cin >> type >> a >> b;  
  147.  
  148. 		if (type == 1) {
  149. 			int g1, g2;  
  150. 			cin >> g1 >> g2; 
  151. 			cout << (solve1(a, b, g1, g2) ? "yes" : "no") << '\n';  
  152. 		}
  153. 		else {
  154. 			int c; 
  155. 			cin >> c;
  156. 			cout << (solve2(a, b, c) ? "yes" : "no") << '\n'; 
  157. 		}
  158. 	}
  159. }
Success #stdin #stdout 0.01s 9320KB
comments (?)
stdin
copy 
13 15
1 2
2 3
3 5
2 4
4 6
2 6
1 4
1 7
7 8
7 9
7 10
8 11
8 12
9 12
12 13
5
1 5 13 1 2
1 6 2 1 4
1 13 6 7 8
2 13 6 7
2 13 6 8
stdout
copy 
yes
yes
yes
no
yes
https://ideone.com/1f87wp
language:
C++14 (gcc 8.3)
created:
263 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!