Cod sursa(job #745104)

Utilizator fhandreiAndrei Hareza fhandrei Data 10 mai 2012 15:55:30
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.91 kb
//Include
#include <fstream>
#include <vector>
using namespace std;

//Constante
const int MAX_SIZE = (int)5e4 + 1;

//Functii
void dfs(int node);

//Variabile
ifstream in("sortaret.in");
ofstream out("sortaret.out");

int nodes, edges;
int visited[MAX_SIZE];

vector<int> before[MAX_SIZE], after[MAX_SIZE];

//Main
int main()
{
	in >> nodes >> edges;
	
	int from, to;
	while(edges--)
	{
		in >> from >> to;
		after[from].push_back(to);
		before[to].push_back(from);
	}
	
	for(int i=1 ; i<=nodes ; ++i)
		dfs(i);
	
	in.close();
	out.close();
	return 0;
}

void dfs(int node)
{
	if(visited[node])
		return ;
	vector<int>::iterator it=before[node].begin(), end = before[node].end();
	
	for(; it!=end ; ++it)
		if(!visited[*it])
			return ;
	
	visited[node] = true;
	out << node << ' ';
	
	it=after[node].begin(), end = after[node].end();
	
	for(; it!=end ; ++it)
		dfs(*it);
}