Cod sursa(job #963114)

Utilizator antonioteoZait Teodor Antonio antonioteo Data 16 iunie 2013 16:30:24
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.72 kb
#include <fstream>
#include <vector>
using namespace std;
const char iname[] = "sortaret.in";
const char oname[] = "sortaret.out";
ifstream fin(iname);
ofstream fout(oname);
int N, M, X, Y, i, j;
vector <int> v[50004];
vector <int> Sorted;
bool viz[50004];
void DFS(int nod){
	vector <int> :: iterator it;
	viz[nod] = true;
	for (it = v[nod].begin(); it != v[nod].end(); ++it)
		if (!viz[*it]) DFS(*it);
	Sorted.push_back(nod);
}
int main(){
	fin >> N >> M;
	while (M--){
		fin >> X >> Y;
		v[X].push_back(Y);
	}
	for (i = 1; i <= N; ++i)
		if (!viz[i]) DFS(i);
	vector <int> :: reverse_iterator it;
	for (it = Sorted.rbegin(); it != Sorted.rend(); ++it)
		fout << *it << ' ';
	fout << '\n';
	return 0;
}