Cod sursa(job #632962)

Utilizator antoanelaAntoanela Siminiuc antoanela Data 12 noiembrie 2011 16:22:03
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.6 kb
#include <cstdio>
#include <vector>
using namespace std;
#define nmax 50010

int n, m, q[nmax], grint[nmax];
vector <int> g[nmax];

int main()
{
	freopen("sortaret.in","r",stdin);
	freopen("sortaret.out","w",stdout);
	scanf("%d %d", &n, &m);
	int i, x, y, nod, v, j;
	for (i=1; i<=m; i++)
	{
		scanf("%d %d", &x, &y);
		g[x].push_back(y);
		grint[y]++;
	}
	for (i=1; i<=n; i++) 
		if (!grint[i]) q[++q[0]]=i;
	for (i=1; i<=q[0]; i++)
	{
		nod=q[i];
		printf("%d ",nod);
		for (j=0; j<g[nod].size(); j++)
		{
			v=g[nod][j];
			grint[v]--;
			if (!grint[v]) q[++q[0]]=v;
		}
	}
}