Cod sursa(job #399602)

Utilizator Omega91Nicodei Eduard Omega91 Data 20 februarie 2010 19:39:38
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.78 kb
#include <fstream>
#include <cstdio>
#include <vector>

using namespace std;

const int NMAX = 50001;
typedef unsigned short t_el;

int main()
{
	vector<t_el> G[NMAX];
	vector<t_el> X;
	int N;

	ifstream f1("sortaret.in");
	freopen("sortaret.out", "w", stdout);
	int m;
	t_el deg[NMAX] = {};
	
	f1 >> N >> m;
	do {
		t_el a, b;
		f1 >> a >> b;
		G[a].push_back(b);
		++deg[b];
	} while(--m);
	
	t_el q[NMAX] = {}, l = 0, r = 0, c;
	for (int i = 1; i <= N; ++i)
		if (!deg[i]) q[r++] = i;
	while(l != r) {
		X.push_back(c = q[l++]);
		for (vector<t_el>::iterator it = G[c].begin();
		     it != G[c].end();
		     ++it) {
			if (!(--deg[*it])) q[r++] = *it;
		}
		G[c].clear();
	}
	for (vector<t_el>::iterator it = X.begin(); it != X.end(); ++it)
		printf("%d ", *it);
	printf("\n");
	return 0;
}