Cod sursa(job #1698307)

Utilizator GeorginskyGeorge Georginsky Data 4 mai 2016 06:44:21
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.67 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
#include <bitset>
#define nmax 50005
using namespace std;
ifstream in("sortaret.in");
ofstream out("sortaret.out");
vector<int> v[nmax];
stack<int> sortedNodes;
int n, m;
bitset<nmax> vz;

void read(){
	in>>n>>m;
	int x, y;
	for(int i=1; i<=m; i++){
		in>>x>>y;
		v[x].push_back(y);	
	}
}

void dfs(int x){
	vz[x]=1;
	for(unsigned int i=0; i<v[x].size(); i++){
		if(!vz[v[x][i]])dfs(v[x][i]);
	}
	sortedNodes.push(x);
} 

void init(){
	for(int i=1; i<=n; i++){
		if(!vz[i])dfs(i);
	}
	while(!sortedNodes.empty()){
		out<<sortedNodes.top()<<" ";
		sortedNodes.pop();
	}
}

int main(){
	read();
	init();
	return 0;
}