fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. const int maxn = 1000 + 20;
  5. const int maxm = 50000 + 20;
  6.  
  7. struct Arc {
  8. 	int from, to, val;
  9. 	Arc() {}
  10. 	Arc(int from, int to, int val):from(from), to(to), val(val) {}
  11. };
  12. vector<Arc> arc;
  13. int n, m;
  14. bool dead[maxn];
  15.  
  16. vector<int> G[maxn];
  17. /*{ SCC*/
  18. int pre[maxn], lowlink[maxn], sccno[maxn], vex_cnt[maxn], dfs_clock, scc_cnt;
  19. stack<int> S;
  20. void dfs(int u) {
  21. 	pre[u] = lowlink[u] = ++dfs_clock;
  22. 	S.push(u);
  23. 	for(size_t i = 0; i < G[u].size(); ++i) {
  24. 		int v = G[u][i];
  25. 		if(!pre[v]) {
  26. 			dfs(v);
  27. 			lowlink[u] = min(lowlink[u], lowlink[v]);
  28. 		} else if(!sccno[v]) {
  29. 			lowlink[u] = min(lowlink[u], pre[v]);
  30. 		}
  31. 	}
  32. 	if(lowlink[u] == pre[u]) {
  33. 		scc_cnt++;
  34. 		int x;
  35. 		do {
  36. 			x = S.top(); S.pop();
  37. 			sccno[x] = scc_cnt;
  38. 			vex_cnt[scc_cnt]++;
  39. 		} while(u != x);
  40. 	}
  41. }
  42. void find_scc() {
  43. 	dfs_clock = scc_cnt = 0;
  44. 	memset(sccno, 0, sizeof sccno);
  45. 	memset(pre, 0, sizeof pre);
  46. 	memset(vex_cnt, 0, sizeof vex_cnt);
  47. 	for(int i = 1; i <= n; ++i) {
  48. 		if(!pre[i]) dfs(i);
  49. 	}
  50. }
  51. /*}*/
  52.  
  53. void kill(int u) {
  54. 	dead[u] = 1;
  55. 	for(size_t i = 0; i < G[u].size(); ++i) {
  56. 		if(!dead[G[u][i]]) {
  57. 			kill(G[u][i]);
  58. 		}
  59. 	}
  60. }
  61.  
  62.  
  63.  
  64. int main() {
  65. 	scanf("%d%d", &n, &m);
  66. 	for(int i = 1; i <= m; ++i) {
  67. 		int a, b, c;
  68. 		scanf("%d%d%d", &a, &b, &c);
  69. 		arc.push_back(Arc(a, b, c));
  70. 		if(c == 0) {
  71. 			if(a == b) {
  72. 				dead[a] = true;
  73. 			} else {
  74. 				G[a].push_back(b);
  75. 			}
  76. 		}
  77. 	}
  78. 	find_scc();
  79. 	for(int i = 1; i <= n; ++i) {
  80. 		G[i].clear();
  81. 	}
  82. 	for(size_t i = 0; i < arc.size(); ++i) {
  83. 		G[arc[i].from].push_back(arc[i].to);
  84. 	}
  85. 	for(int i = 1; i <= n; ++i) {
  86. 		if(1 < vex_cnt[sccno[i]] || dead[i]) {
  87. 			kill(i);
  88. 		}
  89. 	}
  90. 	for(int i = 1; i <= n; ++i) {
  91. 		printf("%d\n", !dead[i]);
  92. 	}
  93. 	return 0;
  94. }
  95.  
  96.  
Success #stdin #stdout 0s 3508KB
comments (?)
stdin
copy 
6 8 
1 2 1 
4 3 0 
2 4 0 
4 3 1 
1 6 0 
6 3 1 
3 2 0 
4 5 1000000000
stdout
copy 
1
0
0
0
0
1
https://ideone.com/viKDho
SGU 219. Synchrograph
language:
C++ (gcc 8.3)
created:
10 years ago
visibility:
public

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!