Cod sursa(job #333087)

Utilizator tamas_iuliaTamas Iulia tamas_iulia Data 21 iulie 2009 14:19:43
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.77 kb
#include <stdio.h>
#include <vector>
using namespace std;

#define Nmax 50005

vector<int> A[Nmax];
int grad[Nmax],Q[Nmax];
int n,m,x,y,i;

void read(){
	freopen("sortaret.in","r",stdin);
   freopen("sortaret.out","w",stdout);
   scanf("%d%d",&n,&m);
   for(int i=1;i<=m;++i){
   	scanf("%d%d",&x,&y);
      A[x].push_back(y);
      grad[y]++;
   }
}

void work(){
	int i,x;
   for(i=1;i<=n;++i)
     if(grad[i] == 0) Q[++Q[0]]=i;

   vector<int>:: iterator it;
   for(i=1;i<=n;++i){
   	x=Q[i];
      for(it=A[x].begin(); it != A[x].end(); ++it){
      	grad[*it]--;
         if(grad[*it] == 0) Q[++Q[0]]=*it;
      }
   }
}

int main(){
	read();
   work();

   for(i=1;i<=n;++i) printf("%d ",Q[i]);
	fclose(stdin);fclose(stdout);
   return 0;
}