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. const int M = 1e5 + 5; 
  13. const int MAX_W = 1e6 + 5; 
  14.  
  15. // Đây là một bài ý tưởng tuy đơn giản nhưng cài đặt lại khá phức tạp
  16. // Đầu tiên ta nhóm các cạnh có cùng trọng số lại chung một nhóm
  17. // sau đó duyệt qua từng nhóm cạnh tăng dần theo trọng số
  18. // Khi xét đến nhóm cạnh có trọng số = w, gọi T là MST (T có thể là rừng) đã dựng được trước đó (dùng các cạnh có trong các nhóm cạnh từ 1 đến w - 1):
  19. // Để đơn giản thì mỗi thành phần liên thông (cây) trong T ta sẽ coi như một đỉnh
  20. // Xét các cạnh e có trong nhóm cạnh hiện tại:
  21. // - Nếu e nối giữa 2 đỉnh u, v đã chung TLPT thì ta kết luận ngay e là "none"
  22. // - Ngược lại ta thêm e vào đồ thị
  23. // - Lưu ý đồ thị được xét dưới dạng mỗi thành phần liên thông là một đỉnh, nên khi thêm thì ta sẽ thêm cạnh (findSet(u), findSet(v))
  24. // Sau khi dựng đồ thị, có thể chứng minh được rằng những cạnh e là cầu thì đáp án sẽ là "any", còn ngược lại sẽ là "at least one"
  25. struct Edge {
  26. 	int u, v, idx;  	
  27. }; 
  28.  
  29. struct dsu {
  30. 	int n; 
  31. 	vector<int> p, sz;  
  32.  
  33. 	dsu(int n): n(n) {
  34. 		p.resize(n);  
  35. 		sz.resize(n);   
  36. 		for (int u = 0; u < n; u++) {
  37. 			p[u] = u;  
  38. 			sz[u] = 1; 
  39. 		}
  40. 	}
  41.  
  42. 	int findSet(int u) {
  43. 		if (p[u] == u) return u;   
  44. 		return p[u] = findSet(p[u]); 
  45. 	}
  46.  
  47. 	void unionSet(int u, int v) {
  48. 		u = findSet(u);  
  49. 		v = findSet(v);   
  50. 		if (u == v) return;
  51. 		if (sz[u] < sz[v]) swap(u, v);  
  52. 		p[v] = u; 
  53. 		sz[u] += sz[v]; 
  54. 	}
  55. }; 
  56.  
  57. int n, m;  
  58. vector<Edge> edges[MAX_W]; 
  59.  
  60. vector<ii> adj[N]; 
  61. int tin[N], low[N], timer;  
  62. bool is_bridge[M];   
  63.  
  64. void dfs(int u, int p) {
  65. 	tin[u] = low[u] = ++timer;    
  66.  
  67. 	bool parent_skipped = true; 
  68. 	for (ii e : adj[u]) {
  69. 		int v = e.first, idx = e.second;  
  70. 		if (v == p && parent_skipped) {
  71. 			parent_skipped = false; 
  72. 			continue;
  73. 		}
  74. 		if (!tin[v]) {
  75. 			dfs(v, u);    
  76. 			low[u] = min(low[u], low[v]); 
  77. 			if (low[v] > tin[u]) is_bridge[idx] = true; 
  78. 		}
  79. 		else {
  80. 			low[u] = min(low[u], tin[v]); 
  81. 		}
  82. 	}
  83. }
  84.  
  85. int ans[M]; // 0: "none", 1: "at least one", 2: "any"
  86.  
  87. int main() {
  88. 	ios::sync_with_stdio(false); 
  89. 	cin.tie(nullptr); 	
  90. 	cin >> n >> m; 
  91.  
  92. 	for (int i = 0; i < m; i++) {
  93. 		int u, v, w; 
  94. 		cin >> u >> v >> w; 
  95. 		edges[w].push_back({u, v, i}); 
  96. 	}
  97.  
  98. 	memset(ans, -1, sizeof ans);  
  99.  
  100. 	dsu DSU(n + 1); 
  101. 	for (int w = 1; w < MAX_W; w++) {
  102. 		// Những cạnh e nối giữa 2 đỉnh u, v chung thành phần liên thông thì ta kết luận được ngay e là "none"
  103. 		// Ngược lại thêm e vào đồ thị 
  104. 		for (Edge e : edges[w]) {
  105. 			int u = DSU.findSet(e.u), v = DSU.findSet(e.v), idx = e.idx;  
  106. 			if (u == v) {
  107. 				ans[idx] = 0;  
  108. 			}
  109. 			else {
  110. 				adj[u].push_back({v, idx});  
  111. 				adj[v].push_back({u, idx}); 
  112. 			}
  113. 		}
  114.  
  115. 		// Dùng kiến thức liên quan đến cây dfs để xác định các cạnh cầu
  116. 		// Lưu ý đồ thị có thể có nhiều đỉnh nhưng lại rất ít cạnh
  117. 		// Nên cần duyệt một cách khôn khéo, cụ thể ta sẽ duyệt theo cạnh
  118. 		// Lưu ý thêm nữa đồ thị lúc này có thể là đa đồ thị (giữa 2 đỉnh có thể có nhiều cạnh nối)
  119. 		timer = 0; 
  120. 		for (Edge e : edges[w]) {
  121. 			int u = DSU.findSet(e.u), v = DSU.findSet(e.v), idx = e.idx;  
  122. 			if (ans[idx] == -1) { 
  123. 				if (!tin[u]) dfs(u, -1); 
  124. 				if (!tin[v]) dfs(v, -1); 
  125. 			}
  126. 		}
  127.  
  128. 		// Chốt đáp án cũng như reset lại thông tin cho lần duyệt nhóm cạnh tiếp theo
  129. 		for (Edge e : edges[w]) {
  130. 			int u = DSU.findSet(e.u), v = DSU.findSet(e.v), idx = e.idx;  
  131. 			if (ans[idx] == -1) {
  132. 				ans[idx] = (is_bridge[idx]) ? 2 : 1;   
  133. 				tin[u] = low[u] = 0;   
  134. 				tin[v] = low[v] = 0;  
  135. 				adj[u].clear();  
  136. 				adj[v].clear();   
  137. 			}
  138. 		}
  139.  
  140. 		// Khi đã xác định được đáp án cho các cạnh có trong nhóm cạnh hiện tại rồi 
  141. 		// thì ta mới thêm các cạnh vào cây MST T 
  142. 		for (Edge e : edges[w]) {
  143. 			int u = e.u, v = e.v;  
  144. 			DSU.unionSet(u, v); 
  145. 		}
  146. 	}
  147.  
  148. 	for (int i = 0; i < m; i++) {
  149. 		if (ans[i] == 0) cout << "none"; 
  150. 		if (ans[i] == 1) cout << "at least one"; 
  151. 		if (ans[i] == 2) cout << "any";
  152. 		cout << '\n'; 
  153. 	}
  154. }
Success #stdin #stdout 0.02s 29988KB
comments (?)
stdin
copy 
4 5
1 2 101
1 3 100
2 3 2
2 4 2
3 4 1
stdout
copy 
none
any
at least one
at least one
any
https://ideone.com/MmK9Ps
language:
C++14 (gcc 8.3)
created:
239 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!