fork download
copy 
  1. // Enjoy your stay.
  2.  
  3. #include <bits/stdc++.h>
  4.  
  5. #define EPS 1e-9
  6. #define INF 1070000000LL
  7. #define MOD 1000000007LL
  8. #define fir first
  9. #define foreach(it,X) for(auto it=(X).begin();it!=(X).end();it++)
  10. #define ite iterator
  11. #define mp make_pair
  12. #define mt make_tuple
  13. #define rep(i,n) rep2(i,0,n)
  14. #define rep2(i,m,n) for(int i=m;i<(n);i++)
  15. #define pb push_back
  16. #define sec second
  17. #define sz(x) ((int)(x).size())
  18.  
  19. using namespace std;
  20.  
  21. typedef istringstream iss;
  22. typedef long long ll;
  23. typedef pair<ll,ll> pi;
  24. typedef stringstream sst;
  25. typedef vector<ll> vi;
  26.  
  27. const int N = 100010;
  28.  
  29. int n, m;
  30. vi g[N];
  31. vi rg[N];
  32. vi vs;
  33. bool used[N];
  34. int cmp[N], cmpsize[N];
  35.  
  36. void add_edge(int from, int to){
  37. 	g[from].pb(to);
  38. 	rg[to].pb(from);
  39. }
  40.  
  41. void dfs(int v){
  42. 	used[v] = 1;
  43. 	rep(i, sz(g[v])){
  44. 		if(!used[g[v][i]]) dfs(g[v][i]);
  45. 	}
  46. 	vs.pb(v);
  47. }
  48.  
  49. void rdfs(int v, int k){
  50. 	used[v] = 1;
  51. 	cmp[v] = k;
  52. 	rep(i, sz(rg[v])){
  53. 		if(!used[rg[v][i]]) rdfs(rg[v][i], k);
  54. 	}
  55. }
  56.  
  57. int scc(){
  58. 	memset(used, 0, sizeof(used));
  59. 	vs.clear();
  60. 	rep(v, n){
  61. 		if(!used[v])
  62. 		dfs(v);
  63. 	}
  64. 	memset(used, 0, sizeof(used));
  65. 	int k = 0;
  66. 	for(int i = sz(vs) - 1; i >= 0; i--){
  67. 		if(!used[vs[i]]) rdfs(vs[i], k++);
  68. 	}
  69. 	return k;
  70. }
  71.  
  72. int dfs2(int v){
  73. 	used[v] = 1;
  74. 	int res = cmpsize[cmp[v]] == 1;
  75. 	rep(i,sz(g[v])) if(!used[g[v][i]]){
  76. 		res &= dfs2(g[v][i]);
  77. 	}
  78. 	rep(i,sz(rg[v])) if(!used[rg[v][i]]){
  79. 		res &= dfs2(rg[v][i]);
  80. 	}
  81. 	cout << res << endl;
  82. 	return res;
  83. }
  84.  
  85. int main(){
  86. 	cin.tie(0);
  87. 	ios_base::sync_with_stdio(0);
  88.  
  89. 	cin >> n >> m;
  90. 	rep(i, m){
  91. 		int a, b;
  92. 		cin >> a >> b;
  93. 		add_edge(a-1, b-1);
  94. 	}
  95. 	scc();
  96. 	memset(cmpsize, 0, sizeof(cmpsize));
  97. 	rep(i, n){
  98. 		cmpsize[cmp[i]]++;
  99. 	}
  100. 	memset(used, 0, sizeof(used));
  101. 	int ans = n;
  102. 	rep(i, n) if(!used[i]){
  103. 		int x = dfs2(i);
  104. 		cout << x << ' ';
  105. 		ans -= x;
  106. 	}
  107. 	cout << ans << endl;
  108. }
Success #stdin #stdout 0.01s 8656KB
comments (?)
stdin
copy 
4 5
1 2
1 3
1 4
2 3
2 4
stdout
copy 
1
1
1
1
1 3
https://ideone.com/aMUfTP
language:
C++14 (clang 8.0)
created:
1 year 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!