Cod sursa(job #188922)

Utilizator alexeiIacob Radu alexei Data 10 mai 2008 21:34:25
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.91 kb
#include<stdio.h>
#define nmax 50001
#include<vector>

using namespace std;
int nod[nmax],sol[nmax];
vector <int> muchii[nmax];


int main()
{
 freopen("sortaret.in","r",stdin);
 freopen("sortaret.out","w",stdout);
    
 int N,M,solfin=0;
 scanf("%d%d",&N,&M);
 
 int aux1,aux2,i;
 vector<int> :: iterator it;
 vector<int> :: iterator st; //pt gust
 
 for(i=1; i<=M; ++i){
    scanf("%d%d",&aux1,&aux2);
    
    muchii[aux1].push_back(aux2);
    ++nod[aux2];
          
    }
    
 for(i=1; i<=N; ++i){
    
    if( !nod[i] )
    sol[++solfin]=i;
    
    }
    
 for(i=1; i<=N; ++i){
    
    aux1=sol[i];
    st=muchii[aux1].end();   
       
    for(it=muchii[aux1].begin(); it!=st; ++it){
       
     --nod[*it];
     if( !nod[*it] )
     sol[++solfin]=*it;
    
    }  
 }   
 //*/
 for(i=1; i<=N; ++i)
 printf("%d ",sol[i]);
    printf("\n");
    
    return 0;
}