fork(12) download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define REP(i,a,b) for(int i=a;i<=b;i++)
  4. #define pii pair<int,int>
  5. #define MP make_pair
  6. #define pb push_back
  7. #define INF 1e8
  8. #define M(x) memset(x,0,sizeof(x))
  9.  
  10. vector<int> graph[100005],graph1[100005];
  11. int comp[100005],indeg[100005],check[100005],n;
  12.  
  13. void dfs(int s){
  14. 	check[s]=1;
  15. 	for(auto it:graph[s]){
  16. 		if(!check[it]) dfs(it);
  17. 	}
  18. }
  19.  
  20. void dfs1(int s,int cl){
  21. 	comp[s]=cl;
  22. 	for(auto it:graph1[s]){
  23. 		if(!comp[it]) {comp[it]=cl,dfs1(it,cl);}
  24. 	}
  25. }
  26.  
  27. void in() {
  28. 	REP(i,1,n){
  29. 		for(auto it:graph[i]){
  30. 			if(comp[i]!=comp[it]) indeg[comp[it]]++;
  31. 		}
  32. 	}
  33. }
  34.  
  35. void solve(){
  36. 	stack<int> s;
  37. 	REP(i,1,n){
  38. 		if(!check[i]){dfs(i);s.push(i);}
  39. 		}
  40.  
  41. 	int clr=1;
  42. 	while(!s.empty()){
  43. 		int it=s.top();s.pop();
  44. 		dfs1(it,clr);
  45. 		clr++;
  46. 	}
  47.  
  48. 	in();
  49. 	int cnt=0,p;
  50. 	REP(i,1,clr-1){if(!indeg[i]) {cnt++;p=i;}}
  51.  
  52. 	if(cnt==1){vector<int> v; cnt=0;REP(i,1,n) if(comp[i]==p) v.pb(i),cnt++; cout<<cnt<<endl;sort(v.begin(),v.end());for(auto i:v) cout<<i<<" "; cout<<endl;}
  53. 	else
  54. 	cout<<0<<endl;
  55. }
  56.  
  57.  
  58.  
  59. int main(){
  60. 	ios_base::sync_with_stdio(0);
  61. 	cin.tie(0);
  62. 	int t,x,y,a,b;
  63. 	{
  64. 		cin>>n>>x;	
  65. 		M(graph);M(graph1);M(comp);M(indeg);M(check);
  66. 		REP(i,1,n){
  67. 			REP(j,0,x-1){
  68. 				cin>>a>>b;
  69. 				graph1[a].pb(b);
  70. 				graph[b].pb(a);
  71. 			}
  72. 		}
  73. 		solve();
  74. 	}
  75. }
Success #stdin #stdout 0.01s 6980KB
comments (?)
stdin
copy 
5 9
1 2
2 1
1 3
3 1
2 3
3 2
2 5
5 4
4 5
stdout
copy 
2
4 5
https://ideone.com/FONff5
language:
C++14 (gcc 8.3)
created:
8 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!