Advertisement
Guest User

Untitled

a guest
Dec 11th, 2017
60
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.31 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2.  
  3. #define ll long long
  4. #define ld long double
  5. #define pb push_back
  6. #define S second
  7. #define F first
  8.  
  9. using namespace std;
  10.  
  11. vector<int> top,ans,g[3100],gr[3100];
  12. int k=0;
  13. bool used[3100],used1[3100];
  14.  
  15. void dfs(int v)
  16. {
  17. used[v]=1;
  18. top.pb(v);
  19. // cout<<v<<' '<<g[v].size()<<endl;
  20. for(int i=0;i<g[v].size();i++)
  21. {
  22. if(!used[g[v][i]])
  23. {
  24. dfs(g[v][i]);
  25. }
  26. }
  27. }
  28.  
  29. void dfs1(int v)
  30. {
  31. used1[v]=1;
  32. for(int i=0;i<gr[v].size();i++)
  33. {
  34. if(!used1[gr[v][i]])
  35. {
  36. dfs1(gr[v][i]);
  37. }
  38. }
  39. }
  40.  
  41. int main()
  42. {
  43. freopen("input.txt","r",stdin);
  44. freopen("output.txt","w",stdout);
  45. int n,m;
  46. cin>>n>>m;
  47. for(int i=0;i<m;i++)
  48. {
  49. int x,y;
  50. cin>>x>>y;
  51. x--;y--;
  52. g[x].pb(y);
  53. gr[y].pb(x);
  54. }
  55. for(int i=0;i<n;i++)
  56. {
  57. if(!used[i])
  58. {
  59. dfs(i);
  60. // return 0;
  61. }
  62. }
  63. for(int i=n-1;i>=0;i--)
  64. {
  65. if(!used1[top[i]])
  66. {
  67. dfs1(top[i]);
  68. k++;
  69. ans.pb(top[i]);
  70. }
  71. }
  72. cout<<k<<endl;
  73. sort(ans.begin(),ans.end());
  74. for(int i=0;i<ans.size();i++)
  75. {
  76. cout<<ans[i]+1<<' ';
  77. }
  78. cout<<endl;
  79. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement