Cod sursa(job #1199469)

Utilizator vasile_pojogaPojoga Vasile vasile_pojoga Data 19 iunie 2014 15:14:04
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.66 kb
#include <fstream>
#include <vector>
#include <stack>
#include <cstring>
using namespace std;

vector<int> G[50005];
stack<int> S;
bool viz[50005];

void DFS(int);

int main()
{
	int n,m,a,b;
	ifstream fin("sortaret.in");
	ofstream fout("sortaret.out");
	fin>>n>>m;
	for(int i=0;i<m;i++)
	{
		fin>>a>>b;
		G[a].push_back(b);
	}
	memset(viz,false,sizeof(viz));
	for(int i=1;i<=n;i++)
	{
		if(!viz[i])
		{
			DFS(i);
		}
	}
	while(!S.empty())
	{
		fout<<S.top()<<" ";
		S.pop();
	}
	return 0;
}

void DFS(int x)
{
	viz[x] = true;
	for(int i=0;i<G[x].size();i++)
	{
		if(!viz[G[x][i]])
		{
			DFS(G[x][i]);
		}
	}
	S.push(x);
}