Cod sursa(job #396494)

Utilizator GappPaun Catalin Gapp Data 15 februarie 2010 14:33:38
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.86 kb
#include <fstream>
#include <vector>

#define NMAX 50100

using namespace std;

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

vector<int> A[NMAX];
int n, m, Sorted[NMAX], nSort, Viz[NMAX];

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

}

void DFS(int i) {

	for (int j = 0; j < A[i].size(); j++) {
		if (!Viz[A[i][j]]) {
			int x = A[i][j];
			DFS(x);
			Sorted[++nSort] = x;
			Viz[x] = 1;
		}
	}

}

void rezolva() {

	for (int i = 1; i <= n; i++) {
		if (!Viz[i]) {
			DFS(i);
			Sorted[++nSort] = i;
			Viz[i] = 1;
		}
	}

}

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

int main() {

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

	fin.close();
	fout.close();

	return 0;
}