Cod sursa(job #377657)

Utilizator yobunSasaujan Marian yobun Data 25 decembrie 2009 18:49:56
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.89 kb
// sortaret.cpp : Defines the entry point for the console application.

//

 

#include <cstdio>

#include <cstring>

#include <vector>

using namespace std;

#define NMAX 50100


int grad[NMAX],Q[NMAX],N,M;

vector<int> G[NMAX];

void citire()

{

int a,b;

scanf("%d %d",&N,&M);

for(int i=1;i<=M;i++)

{

scanf("%d %d",&a,&b);

G[a].push_back(b);

grad[b]++;

}

}
 
void rezolvare()

{

vector<int>::iterator it;

int x;

for(x=1;x<=N;x++)

if(grad[x]==0)

Q[++Q[0]]=x;
 

for(int i=1;i<=N;i++)

for(it=G[Q[i]].begin();it!=G[Q[i]].end();++it)

{

grad[*it]--;

if(grad[*it] == 0)

Q[++Q[0]] = *it;

}

}

void scriere()

{

for(int i=1;i<=N;i++)

printf("%d ",Q[i]);

}
 
int main()

{

freopen("sortaret.in","r",stdin);

freopen("sortaret.out","w",stdout); 

citire();

rezolvare();

scriere();

return 0;

}