Cod sursa(job #1152686)

Utilizator alexsimi66FMI Simandi Alexandru alexsimi66 Data 24 martie 2014 21:33:15
Problema Sortare topologica Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.77 kb
#include<fstream>
#include<vector>

using namespace std;

#define Nmax 50001
#define Mmax 100001

vector<int>ListaAdiacenta[Nmax];
vector<int>spanac;
int color[Nmax];

void DFS(int a){
	color[a] = 1;
	for (vector<int>::iterator j = ListaAdiacenta[a].begin(); j != ListaAdiacenta[a].end(); j++){
		if (color[*j] == 0)
			DFS(*j);
	}
	color[a] = 2;
	spanac.push_back(a);
}


int main(){
	int n, m, x, y;
	ifstream fin("sortaret.in");
	ofstream fout("sortaret.out");
	fin >> n >> m;
	for (int i = 0; i < m; i++){
		fin >> x >> y;
		ListaAdiacenta[x].push_back(y);
	}
	for (int i = 1; i <= n; i++){
		if (color[i] == 0){
			DFS(i);
		}
	}
	if (!spanac.empty())
	for (int i = spanac.size()-1; i > 0;i--){
		fout << spanac[i] << " ";
	}

	return 0;
}