Cod sursa(job #145459)

Utilizator andrei.12Andrei Parvu andrei.12 Data 28 februarie 2008 20:40:14
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.66 kb
#include<stdio.h>
#include<vector>

using namespace std;

#define lg 50005
#define pb push_back

int n, m, i, x, y, fst[lg], q[lg], nr[lg], nrm;
vector<int> v[lg];
void df(int nod){
	
	fst[nod] = 1;
	for (int i = 0; i < nr[nod]; i ++)
		if (!fst[v[nod][i]])
			df(v[nod][i]);
	
	q[++nrm] = nod;
}
int main()
{
	freopen("sortaret.in", "rt", stdin);
	freopen("sortaret.out", "wt", stdout);
	
	scanf("%d%d", &n, &m);
	
	for (i = 1; i <= m; i ++){
		scanf("%d%d", &x, &y);
		
		nr[x] ++;
		v[x].pb(y);
	}
	
	for (i = 1; i <= n; i ++)
		if (!fst[i])
			df(i);
	
	for (i = n; i; i --)
		printf("%d ", q[i]);
	printf("\n");
	
	return 0;
}