Cod sursa(job #940495)

Utilizator tudorv96Tudor Varan tudorv96 Data 16 aprilie 2013 13:39:40
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.79 kb
#include <fstream>
#include <queue>
#include <vector>
using namespace std;

#define in "sortaret.in"
#define out "sortaret.out"
#define N 50005

queue <int> Q;
vector <int> grad (N, 0), LIST[N], top;
int n, m;

int main ()
{
	ifstream fin (in);
	fin >> n >> m;
	for (int i = 0; i < m; ++i) {
		int x, y;
		fin >> x >> y;
		LIST[x].push_back (y);
		grad[y]++;
	}
	fin.close();
	for (int i = 1; i <= n; ++i)
		if (!grad[i]) {
			Q.push (i);
			top.push_back (i);
		}
	while (Q.size()) {
		int x = Q.front();
		for (unsigned i = 0; i < LIST[x].size(); ++i) {
			grad[LIST[x][i]]--;
			if (!grad[LIST[x][i]]) {
				Q.push (LIST[x][i]);
				top.push_back (LIST[x][i]);
			}
		}
		Q.pop();
	}
	ofstream fout (out);
	for (unsigned i = 0; i < top.size(); ++i)
		fout << top[i] << " ";
	fout.close();
	return 0;
}