Poj Solution 2553

http://poj.org/problem?id=2553

#include"stdio.h"
#include"memory.h"
#include"list"
using namespace std;
long sign[5010];
long st[5010],s;
long ok[5010];
long v;
list<int> out[5000],in[5000];
void find(int a)
{list<int>::iterator iter;
    
    sign[a]=1;
    
    for(iter=out[a].begin();iter!=out[a].end();iter++)
    {
        if(sign[*iter]==0)find(*iter);
    }
    st[s++]=a;
}
int sink;
void find_too(int a)
{list<int>::iterator iter;
    sign[a]=sink;    
    for(iter=in[a].begin();iter!=in[a].end();iter++)
    {    
        if(sign[*iter]!=0&&sign[*iter]!=sink)ok[sign[*iter]]=1;                       
        if(sign[*iter]==0)find_too(*iter);        
    }    
}
int main()
{long e,i,a,b;
    while(1)
    {
        scanf("%ld",&v);
        if(v==0)break;
        scanf("%ld",&e);        
        for(i=0;i<v;i++)
        {
            out[i].clear();
            in[i].clear();
        }
        //mset(edge,0,sizeof(char)*5000*5000);
        for(i=0;i<e;i++)
        {
            scanf("%ld %ld",&a,&b);
            if(a!=b){
                out[a-1].push_back(b-1);
                in[b-1].push_back(a-1);
            }
        }
        s=0;
         memset(sign,0,sizeof(long)*5010);
         for(i=0;i<v;i++)
             if(!sign[i])find(i);
         memset(sign,0,sizeof(long)*5010);
         memset(ok,0,sizeof(long)*5010);         
         sink=1;
         for(i=v-1;i>=0;i--)
         {     
             if(sign[st[i]]==0)
             {find_too(st[i]);
                sink++;
             }
         }
         int key;
         for(i=0,key=0;i<v;i++)
         {     if(ok[sign[i]]==0){if(key)printf(" ");
                                
                                else key=1;
                            
                            printf("%ld",i+1);
                 
                            }
         }
         printf("n");        
    }
    return 0;
}



											
This entry was posted in poj. Bookmark the permalink.

Leave a Reply

Your email address will not be published. Required fields are marked *