Cod sursa(job #745105)

Utilizator fhandreiAndrei Hareza fhandrei Data 10 mai 2012 15:57:29
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.92 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 cFrom, cTo;
	while(edges--)
	{
		in >> cFrom >> cTo;
		after[cFrom].push_back(cTo);
		before[cTo].push_back(cFrom);
	}
	
	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);
}