Cod sursa(job #375156)

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

using namespace std;

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

vector<int> G[NM];

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

int main()
{
    int a,b;
    
    freopen("sortaret.in","r",stdin);
    freopen("sortaret.out","w",stdout);
    
    scanf("%d %d",&N,&M);
    
    FOR(i,1,M)
    {
      scanf("%d %d",&a,&b);
      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;
}