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 = 8e2 + 5; 
  12.  
  13. // Coi mỗi thành phần liên thông mạnh như một nhóm	
  14. // Chỉ cần "nhóm trưởng" biết tin thì cả nhóm đều sẽ biết
  15. // => Nén mỗi thành phần liên thông mạnh thành 1 đỉnh
  16. // Ở đồ thị G' sau khi nén, có nhận xét:
  17. // G' là DAG (đồ thị có hướng không có chu trình) 
  18. // Với một đỉnh u bất kì, nếu tồn tại cung đi vào u thì không việc gì phải truyền tin cho u cả
  19. // ví dụ tồn tại cung v -> u thì thay vì truyền tin cho u thì ta truyền tin cho v sẽ tốt hơn
  20. // => Đáp án chính là số đỉnh có bậc vào = 0
  21. int n, m;  
  22. vector<int> adj[N]; 
  23.  
  24. int num_scc;   
  25. int tin[N], low[N], timer;  
  26. int id[N]; // id[u]: u thuộc thành phần liên thông mạnh nào
  27. vector<int> s;   
  28. bool in_stack[N]; 
  29.  
  30. void dfs(int u) {
  31. 	tin[u] = low[u] = ++timer;   
  32. 	s.push_back(u);   
  33. 	in_stack[u] = true;  
  34.  
  35. 	for (int v : adj[u]) {
  36. 		if (!tin[v]) {
  37. 			dfs(v);  
  38. 		}
  39. 		if (in_stack[v]) {
  40. 			low[u] = min(low[u], low[v]); 
  41. 		}
  42. 	}
  43.  
  44. 	if (low[u] == tin[u]) {
  45. 		num_scc++;   
  46. 		while (true) {
  47. 			int v = s.back(); s.pop_back();  
  48. 			in_stack[v] = false; 
  49. 			id[v] = num_scc;  
  50. 			if (v == u) break; 
  51. 		}
  52. 	}
  53. }
  54.  
  55. int indeg[N]; 
  56.  
  57. int main() {
  58. 	ios::sync_with_stdio(false); 
  59. 	cin.tie(nullptr); 	
  60. 	cin >> n >> m; 
  61.  
  62. 	for (int i = 0; i < m; i++) {
  63. 		int u, v; 
  64. 		cin >> u >> v; 
  65. 		adj[u].push_back(v); 
  66. 	}
  67.  
  68. 	timer = 0; 
  69. 	num_scc = 0; 
  70. 	for (int u = 1; u <= n; u++) {
  71. 		if (!tin[u]) dfs(u); 
  72. 	}
  73.  
  74. 	for (int u = 1; u <= n; u++) {
  75. 		for (int v : adj[u]) {
  76. 			if (id[u] == id[v]) continue;   
  77. 			indeg[id[v]]++; 
  78. 		}
  79. 	}
  80.  
  81. 	int ans = 0; 
  82. 	for (int u = 1; u <= num_scc; u++) {
  83. 		ans += (indeg[u] == 0); 
  84. 	}
  85.  
  86. 	cout << ans << '\n'; 
  87. }
  88.  
Success #stdin #stdout 0s 5284KB
comments (?)
stdin
copy 
12 15
1 3
3 6
6 1
6 8
8 12
12 9
9 6
2 4
4 5
5 2
4 6
7 10
10 11
11 7
10 9
stdout
copy 
2
https://ideone.com/SZuKEu
language:
C++14 (gcc 8.3)
created:
259 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!