Cod sursa(job #387083)

Utilizator bixcabc abc bixc Data 26 ianuarie 2010 19:59:08
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.85 kb
#include <cstdio>
#include <vector>
using namespace std;

#define Nmax 50010

void citire ();
int n, m;
int Q[Nmax], grad[Nmax];
vector <int> V[Nmax];

void sortare_topologica () {
	
	int i, p = 1, u = 0, nod, fiu;
	for (i = 1; i <= n; i++)
		if (!grad[i])
			Q[++u] = i;
	
	while (p <= u) {
		nod = Q[p];
		
		for (i = 0; i < (int) V[nod].size (); i++) {
			fiu = V[nod][i];
			
			grad[fiu]--;
			if (!grad[fiu])
				Q[++u] = fiu;
		}
		
		p++;
	}
}

int main () {

	freopen ("sortaret.in", "r", stdin);
	freopen ("sortaret.out", "w", stdout);

	citire ();
	sortare_topologica ();
	
	for (int i = 1; i <= n; i++)
		printf ("%d ", Q[i]);
	
	return 0;
}

void citire () {
	
	int x, y;
	scanf ("%d %d", &n, &m);
	for (int i = 1; i <= m; i++) {
		scanf ("%d %d", &x, &y);
		V[x].push_back (y);
		grad[y]++;
	}
}