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 = 1e4 + 5; 
  12.  
  13. int n, m;  
  14. vector<int> adj[N]; 
  15.  
  16. // Thuật toán Tarjan
  17. int num_scc; // Số thành phần liên thông mạnh
  18. int tin[N], low[N], timer;  
  19. vector<int> s;   
  20. bool in_stack[N]; 
  21.  
  22. void dfs(int u) {
  23. 	tin[u] = low[u] = ++timer;   
  24. 	s.push_back(u);   
  25. 	in_stack[u] = true;  
  26.  
  27. 	for (int v : adj[u]) {
  28. 		if (!tin[v]) {
  29. 			dfs(v);  
  30. 		}
  31. 		if (in_stack[v]) {
  32. 			low[u] = min(low[u], low[v]); 
  33. 		}
  34. 	}
  35.  
  36. 	if (low[u] == tin[u]) {
  37. 		num_scc++;   
  38. 		while (true) {
  39. 			int v = s.back(); s.pop_back();  
  40. 			in_stack[v] = false; 
  41. 			if (v == u) break; 
  42. 		}
  43. 	}
  44. }
  45.  
  46. int main() {
  47. 	ios::sync_with_stdio(false); 
  48. 	cin.tie(nullptr); 	
  49. 	cin >> n >> m; 
  50.  
  51. 	for (int i = 0; i < m; i++) {
  52. 		int u, v; 
  53. 		cin >> u >> v; 
  54. 		adj[u].push_back(v); 
  55. 	}
  56.  
  57. 	timer = 0; 
  58. 	num_scc = 0; 
  59. 	for (int u = 1; u <= n; u++) {
  60. 		if (!tin[u]) dfs(u); 
  61. 	}
  62.  
  63. 	cout << num_scc << '\n'; 
  64. }
Success #stdin #stdout 0s 5292KB
comments (?)
stdin
copy 
3 2
1 2
2 3
stdout
copy 
3
https://ideone.com/c7xYG3
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!