Cod sursa(job #375163)

Utilizator perticas_catalinperticas catalin perticas_catalin Data 19 decembrie 2009 17:58:02
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.53 kb
#include<iostream>
#include<string>
#include<vector>

using namespace std;

#define PB push_back
#define NM 50005
#define FOR(i,a,b)for(int i=(a);i<=(b);++i)
#define maxbuf 65536

FILE*fin=fopen("sortaret.in","r");

char buf[maxbuf];

int ind,N,M,GI[NM],D[NM],dim;

vector<int> G[NM];

inline void refbuf()
{
       int ans=fread(buf,1,maxbuf,fin);
       if(ans<maxbuf) buf[ans]=0;
       ind=0;
}

inline int readnr()
{
       int ans=0;
       
       one:
           while(ind<maxbuf && !isdigit(buf[ind])) ++ind;
           if(ind==maxbuf)
           {
             refbuf();
             goto one;
           }
           
       two:
           while(ind<maxbuf && isdigit(buf[ind]))
           {
             ans=ans*10+buf[ind]-'0';
             ++ind;
           }    
           if(ind==maxbuf)
           {
             refbuf();
             goto two;
           }
           
       return ans;    
}

int main()
{
    int a,b;
    
    refbuf();
    
    freopen("sortaret.out","w",stdout);
    
    N=readnr();
    M=readnr();
    
    FOR(i,1,M)
    {
      a=readnr();
      b=readnr();
      
      G[a].PB(b);
      ++GI[b];
    }
    
    FOR(i,1,N)
      if(!GI[i]) D[++dim]=i;
      
    FOR(i,1,dim)
    {
      int nod=D[i];
      printf("%d ",nod);
      
      int sz=G[nod].size();
      FOR(j,0,sz-1)
      {
        int nnod=G[nod][j];
        
        --GI[nnod];
        if(!GI[nnod]) D[++dim]=nnod;
      }
    }  
    
    return 0;
}