Cod sursa(job #1704907)

Utilizator perjulucianPerju Lucian Ionut perjulucian Data 19 mai 2016 16:12:47
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.83 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>

using namespace std; 

std::ifstream f("sortaret.in");
std::ofstream g("sortaret.out");

int N, M;
vector<vector<int>> edges;
vector<bool> visited;
stack<int> topSort;

void read(){
	int from,to;
	
	f >> N >> M ;
	
	for(int i = 0 ; i <= N ; ++i){
		edges.push_back(vector<int>());
		visited.push_back(false);
		
	}

	for(int i = 0 ; i < M ; ++i){
		f >> from >> to;
		edges.at(from).push_back(to);
		
	}
}

void dfs(int nod){
	visited[nod] = true;
	for(auto son : edges.at(nod)){
		if(!visited[son]){
			visited[son] = true;
			dfs(son);
		}
	}
	topSort.push(nod);
}

void CC(){
	
	for(int i = 1; i <= N ; ++i){
		if(!visited[i]){
			
			dfs(i);
		}
	}
	
}


int main(){
	read();
	CC();
	while(topSort.size() > 0){
		g << topSort.top() << " ";
		topSort.pop();	
	}
	return 0 ;
}