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 = 5e4 + 5; 
  12.  
  13. // Yêu cầu làm qua trước bài Reachable Nodes
  14. // Bài này chỉ khác là thay vì cho đồ thị DAG thì cho đồ thị có hướng (có thể có chu trình)
  15. // => Nén mỗi thành phần liên thông mạnh thành một đỉnh 
  16. // => Đồ thị sau khi nén là DAG
  17. // Đỉnh a đến được đỉnh b nếu TPLT mạnh chứa a đến được TPLT mạnh chứa b
  18. // => Áp dụng bài Reachable Nodes
  19. int n, m, q;  
  20. vector<int> adj[N]; 
  21.  
  22. int num_scc; 
  23. int tin[N], low[N], timer;   
  24. int id[N]; // id[u] = Số thứ tự của thành phần liên thông mạnh chứa u 
  25. vector<int> st;  
  26. bool in_stack[N]; 
  27.  
  28. void dfs1(int u) {
  29. 	tin[u] = low[u] = ++timer;  
  30. 	st.push_back(u); 
  31. 	in_stack[u] = true;  
  32.  
  33. 	for (int v : adj[u]) {
  34. 		if (!tin[v]) {
  35. 			dfs1(v);  
  36. 		}
  37. 		if (in_stack[v]) {
  38. 			low[u] = min(low[u], low[v]); 
  39. 		}
  40. 	}
  41.  
  42. 	if (low[u] == tin[u]) {
  43. 		num_scc++; 
  44. 		while (true) {
  45. 			int v = st.back(); st.pop_back(); 
  46. 			in_stack[v] = false; 
  47. 			id[v] = num_scc; 
  48. 			if (v == u) break; 
  49. 		}
  50. 	}
  51. }
  52.  
  53. vector<int> g[N]; // Danh sách kề của đồ thị sau khi nén
  54.  
  55. bool vis[N]; 
  56. bitset<N> bs[N]; // bs[u] là bitset đại diện cho tập đỉnh mà u đến được (mỗi thành phần liên thông mạnh được coi là một đỉnh) 
  57.  
  58. void dfs2(int u) {
  59. 	vis[u] = true;  
  60. 	bs[u][u] = 1;  
  61. 	for (int v : g[u]) {
  62. 		if (!vis[v]) dfs2(v); 
  63. 		bs[u] |= bs[v];
  64. 	}
  65. }
  66.  
  67. int main() {
  68. 	ios::sync_with_stdio(false); 
  69. 	cin.tie(nullptr); 	
  70. 	cin >> n >> m >> q; 
  71.  
  72. 	for (int i = 0; i < m; i++) {
  73. 		int u, v; 
  74. 		cin >> u >> v; 
  75. 		adj[u].push_back(v); 
  76. 	}
  77.  
  78. 	timer = 0;  
  79. 	for (int u = 1; u <= n; u++) {
  80. 		if (!tin[u]) dfs1(u);  
  81. 	}
  82.  
  83. 	for (int u = 1; u <= n; u++) {
  84. 		for (int v : adj[u]) {
  85. 			if (id[u] == id[v]) continue; 	
  86. 			g[id[u]].push_back(id[v]); 
  87. 		}
  88. 	}
  89.  
  90. 	for (int u = 1; u <= num_scc; u++) {
  91. 		if (!vis[u]) dfs2(u); 
  92. 	}
  93.  
  94. 	while (q--) {
  95. 		int u, v; 
  96. 		cin >> u >> v; 
  97. 		cout << (bs[id[u]][id[v]] ? "YES" : "NO") << '\n'; 
  98. 	}
  99. }
Success #stdin #stdout 0.01s 6768KB
comments (?)
stdin
copy 
4 4 3
1 2
2 3
3 1
4 3
1 3
1 4
4 1
stdout
copy 
YES
NO
YES
https://ideone.com/Etm75b
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!