Cod sursa(job #376903)

Utilizator ooctavTuchila Octavian ooctav Data 22 decembrie 2009 20:27:51
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.9 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;
}