Cod sursa(job #823731)

Utilizator horeste12Stoianovici Horatiu Andrei horeste12 Data 25 noiembrie 2012 16:29:18
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.73 kb
#include <fstream>
#include <vector>
#include <stack>
using namespace std;

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

int n, m;
vector<vector<int> > G(50010);
stack<int> st;
bool viz[50010];

void readData()
{
	f >> n >> m;
	int x,y;
	for(int i = 1; i <= m; i++)
	{
		f>>x>>y;
		G[x].push_back(y);
	}
	f.close();
}

void DFS(int i)
{
	viz[i]=1;
	for( vector<int>::iterator p = G[i].begin(); p < G[i].end(); p++ )
	{
		if(!viz[*p])
		{
			DFS(*p);
		}
	}
	st.push(i);
}

void writeData()
{
	while(!st.empty())
	{
		g << st.top() << ' ';
		st.pop();
	}
}

int main()
{
	readData();
	for(int i = 1; i <= n; i++)
	{
		if(!viz[i])
		{
			DFS(i);
		}
	}
	writeData();
	return 0;
}