Cod sursa(job #304004)

Utilizator scvalexAlexandru Scvortov scvalex Data 10 aprilie 2009 18:11:45
Problema Sortare topologica Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.68 kb
#include <fstream>
#include <iostream>
#include <list>
#include <set>
#include <vector>

using namespace std;

#define tr(C, i) for (typeof((C).begin()) i = (C).begin(); i != (C).end(); ++i)

vector< set<int> > G;
vector<bool> viz;
list<int> O;

void dfs(int u) {
	tr(G[u], vv)
		dfs(*vv);
	viz[u] = true;
	O.push_front(u);
}

int main(int argc, char *argv[]) {
	int N, M, u, v;

	ifstream fin("sortaret.in");
	fin >> N >> M;
	G.resize(N+1);
	while (M--) {
		fin >> u >> v;
		G[u].insert(v);
	}
	fin.close();

	viz.resize(N+1);
	for (int u = 1; u <= N; ++u)
		if (!viz[u])
			dfs(u);

	ofstream fout("sortaret.out");
	tr(O, uu)
		fout << *uu << " ";
	fout << endl;
	fout.close();

	return 0;
}