Cod sursa(job #566418)

Utilizator pykhNeagoe Alexandru pykh Data 28 martie 2011 22:43:17
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.75 kb
#include<cstdio>
#include<vector>
using namespace std;

const char in[]="sortaret.in";
const char out[]="sortaret.out";

const int Max_N = 50100;
#define pb push_back

int d[Max_N], Q[Max_N], N, M, X, Y;
vector<int>G[Max_N];

int main()
	{
		freopen(in,"r",stdin);
		freopen(out,"w",stdout);
		scanf("%d%d", &N, &M);
		for(int i = 1 ; i <= M ; ++i)
			{
				scanf("%d%d", &X, &Y);
				G[X].pb(Y);
				++d[Y];
		}
		
		for(int i = 1 ; i <= N ; ++i)
			if(!d[i])Q[++Q[0]] = i;
		
		for(int i = 1 ; i <= N ; ++i)
		{
			X = Q[i];
			for(unsigned i = 0 ; i < G[X].size() ; ++i)
			{
				--d[ G[ X ][ i ] ];
				if(!d[ G[ X ][ i ] ])Q[++Q[0]] = G[ X ][ i ];
			}
		}
		for(int i = 1 ; i <= N ; ++i)
			printf("%d ", Q[i]);
		return 0;
}