fork download
copy 
  1. #include<stdio.h>
  2. #include<iostream>
  3. #include<vector>
  4. #include<stack>
  5. #include<set>
  6. #include<algorithm>
  7. using namespace std;
  8. #define gc getchar_unlocked
  9. int read_int() {
  10.   char c = gc();
  11.   while(c<'0' || c>'9') c = gc();
  12.   int ret = 0;
  13.   while(c>='0' && c<='9') {
  14.     ret = 10 * ret + c - 48;
  15.     c = gc();
  16.   }
  17.   return ret;
  18. }
  19. int visited[5001];
  20. vector<int> myvector[5001];
  21. stack<int> mystack;
  22. int graph[5001];
  23. int ans[5001];
  24. int disc[5001];
  25. int low[5001];
  26. int tim,id;
  27. void connected(int u)
  28. {
  29.  
  30.     disc[u]=low[u]=++tim;
  31.     visited[u]=1;
  32.     mystack.push(u);
  33.     vector<int>::iterator it;
  34.     int v;
  35.     for(it=myvector[u].begin();it!=myvector[u].end();it++)
  36.     {
  37.         v=*it;
  38.         if(visited[v]==0)
  39.         {
  40.         connected(v);
  41.         low[u]=min(low[u],low[v]);
  42.         }
  43.         else
  44.         {
  45.             low[u]=min(disc[v],low[u]);
  46.         }
  47.     }
  48.  
  49.     if(disc[u]==low[u])
  50.     {
  51.         id++;
  52.         int i;
  53.         while(mystack.top()!=u)
  54.         {
  55.             i=mystack.top();
  56.             mystack.pop();
  57.             graph[i]=id;
  58.         }
  59.          i=mystack.top();
  60.             mystack.pop();
  61.             graph[i]=id;
  62.     }
  63. }
  64. int main()
  65. {
  66.     int n,m,i,l,r;
  67.     vector<int>::iterator it;
  68.     while(1)
  69.     {
  70.         n=read_int();
  71.         if(n==0)
  72.             return 0;
  73.         m=read_int();
  74.         for(i=1;i<=m;i++)
  75.         {
  76.             l=read_int();
  77.             r=read_int();
  78.             myvector[l].push_back(r);
  79.         }
  80.         tim=0,id=0;
  81.         for(i=1;i<=n;i++)
  82.         {
  83.             if(visited[i]==0)
  84.                 connected(i);
  85.         }
  86.         for(i=1;i<=n;i++)
  87.         {
  88.             for(it=myvector[i].begin();it!=myvector[i].end();it++)
  89.             {
  90.                 if(graph[i]!=graph[*it])
  91.                 {
  92.                     ans[graph[i]]=1;
  93.                     break;
  94.                 }
  95.             }
  96.         }
  97.         for(i=1;i<=n;i++)
  98.         {
  99.        if(ans[graph[i]]==0)
  100.         printf("%d ",i);
  101.         myvector[i].clear();
  102.         visited[i]=0;
  103.         graph[i]=0;
  104.         disc[i]=0;
  105.         low[i]=0;
  106.         }
  107.         for(i=1;i<=n;i++)
  108.             ans[i]=0;
  109.      printf("\n");
  110.     }
  111.     return 0;
  112. }
  113.  
Success #stdin #stdout 0s 3636KB
comments (?)
stdin
copy 
5 5
1 2 2 3 3 1 4 5 5 4
0
stdout
copy 
1 2 3 4 5
https://ideone.com/2yy842
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!