Cod sursa(job #482167)

Utilizator Addy.Adrian Draghici Addy. Data 2 septembrie 2010 18:22:01
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.9 kb
#include <cstdio>
#include <vector>

using namespace std;

const int NMAX = 50050;

int Q[NMAX], grd[NMAX], n, m;
vector <int> G[NMAX];

void citire (), sortare_t (), afisare ();

int main () {
	
	citire ();
	
	sortare_t ();
	
	afisare ();
	
	return 0;
}

void citire () {
	
	freopen ("sortaret.in", "r", stdin);
	
	int i, x, y;
	
	scanf ("%d %d", &n, &m);
	
	for (i = 1; i <= m; i++) {
		scanf ("%d %d", &x, &y);
		G[x].push_back (y), grd[y]++;
	}
}

void sortare_t () {
	
	int i, p, nod, fiu, N = 0;
	
	for (i = 1; i <= n; i++)
		if (!grd[i])
			Q[++N] = i;
	
	for (p = 1; N < n; p++) {
		nod = Q[p];
		for (i = 0; i < (int) G[nod].size (); i++) {
			fiu = G[nod][i];
			grd[fiu]--;
			if (!grd[fiu])
				Q[++N] = fiu;
		}
	}
}

void afisare () {
	
	freopen ("sortaret.out", "w", stdout);
	
	int i;
	
	for (i = 1; i <= n; i++)
		printf ("%d ", Q[i]);
}