Cod sursa(job #629742)

Utilizator the_snyper06FMI - ALexandru Mihai the_snyper06 Data 3 noiembrie 2011 21:41:29
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.71 kb
#include<cstdio>
#include<vector>

using namespace std;

int n, m, grad[50001];
vector <int> L, S, graf[50001];

void Sortare() {
	int i, k, p;
	unsigned int j, v;
	
	for(i = 1; i <= n; i++)
		if(grad[i] == 0) S.push_back(i);
	
	j = 0;
	while(j < S.size()) {
		k = S[j++];
		L.push_back(k);
		
		v = 0;
		while(v < graf[k].size()) {
			p = graf[k][v++], grad[p]--;
			if(grad[p] == 0) S.push_back(p);
		}
	}
	
	for(j = 0 ; j < L.size(); j++) printf("%d ", L[j]);
}

int main() {
	
	int i, x, y;
	
	freopen("sortaret.in", "r", stdin), freopen("sortaret.out", "w", stdout);
	scanf("%d %d", &n, &m);
	for(i = 1; i <= m; i++)
	{
		scanf("%d %d", &x, &y);
		graf[x].push_back(y);
		grad[y]++;
	}
	
	Sortare();
	
	return 0;
}