fork(2) download
copy 
  1. # include <iostream>
  2. # include <stdio.h>
  3. # include <algorithm>
  4. # include <queue>
  5. # include <set>
  6. # include <string.h>
  7. # include <vector>
  8. # include <fstream>
  9. # include <math.h>
  10. # include <sstream>
  11. # include <stack>
  12.  
  13. # define for1(i,k,n)              for(long long i=k;i<n;i++)
  14. # define for2(i,k,n)              for(long long i=k;i<=n;i++)
  15. # define Min(x,y)                   ((x)<(y)?(x):(y))
  16. # define Max(x,y)                   ((x)>(y)?(x):(y))
  17. # define INF (long long int ) 1e15
  18. # define ALL(x)                  (begin(x),end(x))
  19. # define Abs(x)                 (x>=0?x:-x)
  20.  
  21. using namespace std;
  22. typedef long long int ll;
  23.  
  24. ll t;
  25.  
  26. vector < vector <int> >  g;
  27. vector <int> status;
  28. vector <int> status2;
  29. vector <int> status3;
  30. vector <bool> v1;
  31. vector <int> reach;
  32. stack <int> global;
  33. ll d1;
  34. void dfs (int x)
  35. { ll y;
  36. 	if (status[x]!=0)
  37. 		return;
  38. 	reach[x]=1;
  39. 	++t;
  40. 	global.push(x);
  41. 	status2[x]=t;
  42. status3[x]=t;
  43. if (status[x]==0)
  44. {
  45. 	status[x]=1;
  46. 	for1(i,0,g[x].size())
  47. 	dfs(g[x][i]);
  48. }
  49. status [x]=2;
  50.  
  51. for1(i,0,g[x].size())
  52. {
  53.  status2[x]=Min(status2[x],status2[g[x][i]]); 
  54.  
  55. }
  56. if (status2[x]==status3[x])
  57. {  
  58. while (global.top()!=x)
  59. {   
  60. 	y=global.top();
  61. 	global.pop();
  62. 	if (d1==-1)
  63. 		v1[y]=true;
  64. 	// cout<<y<<" ";
  65. } 
  66. // cout<<x<<endl;
  67. if (d1==-1)
  68. v1[x]=true;
  69. global.pop();
  70. d1=0;
  71. }
  72. return;
  73. }
  74.  
  75.  
  76.  
  77.  
  78.   int main()
  79. {
  80.  #ifndef ONLINE_JUDGE
  81.     freopen("in.txt", "r", stdin);
  82.      freopen("out.txt", "w", stdout);
  83. #endif
  84.     std::ios_base::sync_with_stdio (false);
  85.  
  86.     ll i,j,k,x,y,l,n,m,e,v,sum1;
  87.  
  88. while ((cin>>v)&&(v!=0))
  89. {
  90. 	t=0;
  91. reach.clear();
  92. reach.resize(v+1,0);
  93. 	g.clear();
  94.    status.clear();
  95.    g.resize(v+1);
  96.    status.resize(v+1);
  97.   fill(status.begin(),status.end(),0);
  98.    status2.clear();
  99.    status3.clear();
  100.    status2.resize(v+1);
  101.    status3.resize(v+1);
  102.    v1.clear();
  103.    v1.resize(v+1);
  104.    fill(v1.begin(),v1.end(),0);
  105. cin>>e;
  106. for1(i,0,e)
  107. {
  108. 	cin>>x>>y;
  109. 	g[x].push_back(y);
  110. }
  111. while(!global.empty())
  112. global.pop();
  113.  
  114. for1(i,1,v+1)
  115. {
  116. 	if (status[i]==0)
  117. 	{d1=-1;
  118. 		while(!global.empty())
  119. global.pop();
  120. 		dfs(i);
  121. 	}
  122.  
  123. }
  124.  
  125. for1(i,1,v+1)
  126. if (v1[i])
  127. 	 cout<<i<<" ";
  128.  cout<<endl;
  129. }
  130. return 0;
  131. }
Success #stdin #stdout 0s 2824KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/Qe6BmJ
language:
C++ 4.3.2 (gcc-4.3.2)
created:
10 years 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!