Cod sursa(job #472511)

Utilizator IrnukIrina Grosu Irnuk Data 25 iulie 2010 14:51:48
Problema Sortare topologica Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.99 kb
#include<fstream>
#include<vector>
#include<list>
#include<stack>

#define NMAX 100005

using namespace std;

long n,m,vizitat[NMAX];
stack<long> S;

struct nod
{
	long varf;
	//long cost;
	nod(){}
	nod(long nvarf) : varf(nvarf){}
};

vector<list<nod>> G;

void dfs(long x)
{
	list<nod>::iterator itr;
	for(itr=G[x].begin(); itr!=G[x].end(); itr++)
	{
		if(vizitat[(*itr).varf]==0)
		{
			vizitat[(*itr).varf]=1;
			dfs((*itr).varf);
		}
	}
	S.push(x);
}

void topologicalSort()
{

	long i;
	for(i=1;i<=n;i++)
		if(vizitat[i]==0)
		{	
			vizitat[i]=1;
			dfs(i);
		}
}

int main()
{
	fstream fin,fout;
	long i,x,y,c;

	fin.open("dag.in",ios::in);
	fout.open("dag.out",ios::out);
	list<nod> lista;

	fin>>n>>m;
	for(i=0;i<=n;i++)
		G.push_back(lista);

	for(i=0;i<m;i++)
	{
		fin>>x>>y;
		G[x].push_back(nod(y));
	}

	topologicalSort();

	while(!S.empty())
	{
		fout<<S.top()<<" ";
		S.pop();
	}
	fin.close();
	fout.close();
	return 0;
}