Cod sursa(job #1756635)

Utilizator irinapatularuPatularu Irina irinapatularu Data 13 septembrie 2016 11:35:44
Problema Sortare topologica Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.78 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <list>
#include <stack>

#define NMAX 50001

using namespace std;
int N, M;
int visited[NMAX];
vector<list <int> > adList(NMAX);
stack<int> S;

void dfs(int node){
	visited[node] = 1;

	list<int> :: iterator it = adList[node].begin();
	while(it != adList[node].end()){
		int neigh = *it;
		if(visited[neigh] == 0)
			dfs(neigh);
		it++;
	}
	S.push(node);
}
int main(){
	int a, b;
	ifstream f("sortaret.in");
	ofstream g("sortaret.out");

	f >> N >> M;
	for(int i = 1; i <= M; i++){
		f >> a >> b;
		adList[a].push_back(b);
		adList[b].push_back(a);
	}
	f.close();

	for(int i = 1; i <= N; i++)
		if(visited[i] == 0)
			dfs(i);

	while(!S.empty()){
		int value = S.top();
		S.pop();
		g << value << " ";

	}
	g.close();
	return 0;
}