Cod sursa(job #342075)

Utilizator digital_phreakMolache Andrei digital_phreak Data 20 august 2009 15:48:48
Problema Sortare topologica Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.71 kb
#include <iostream>
#include <vector>

using namespace std;

long N,M;
vector<int> nodes[50001];
int deg[50001];
int Q[50001];

int main() {
	
	freopen("sortaret.in","r",stdin);
	freopen("sortaret.out","w",stdout);
	
	scanf("%d%d",&N,&M);
	
	int x,y;
	
	for (int i=0;i<M;++i) {
		scanf("%d%d",&x,&y);
		nodes[x].push_back(y);
		deg[y]++;
	}
	
	for (int i=1;i<=N;++i)
		if (deg[i] == 0) Q[++Q[0]] = i;
		
	for (int i=1;i<=N;++i) {
		x = Q[i];
		for (vector<int>::iterator it = nodes[x].begin(); it != nodes[x].end(); ++it) {
			deg[*it]--;
			if (deg[*it] == 0) Q[Q[0]++] = *it;
		}
	}
	
	for (int i=1;i<=N;++i) printf("%d ",Q[i]);
	
	fclose(stdin);
	fclose(stdout);

	return 0;
}