Cod sursa(job #396491)

Utilizator UpL1nKPaunescu Sorin UpL1nK Data 15 februarie 2010 14:30:44
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.78 kb
#include <fstream>
#include <vector>

#define NMAX 50100

using namespace std;

vector <int> a[NMAX];
int n, m;
int used[NMAX], sol[NMAX], num;

ifstream fin("sortaret.in");
ofstream fout("sortaret.out");

void citire() {

	fin >> n >> m;
	int x, y;
	for (int i = 1; i <= m; i++) {
		fin >> x >> y;
		a[x].push_back(y);
	}
}

void DFS(int i) {
	for (int j = 0; j < a[i].size(); j++)
		if (!used[a[i][j]]) {
			int x = a[i][j];
			DFS(x);
			sol[++num] = x;
			used[x] = 1;
		}
}

void rezolva() {
	int i;
	for (i = 1; i <= n; i++)
		if (!used[i]) {
			DFS(i);
			sol[++num] = i;
			used[i] = 1;
		}
}

void afiseaza() {
	for (int i = n; i >= 1; i--)
		fout << sol[i] <<' ';
}



int main() {

	citire();
	rezolva();
	afiseaza();

	return 0;
}