Cod sursa(job #470353)

Utilizator IrnukIrina Grosu Irnuk Data 13 iulie 2010 14:07:33
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.93 kb
#include<fstream>
#include<list>
#include<vector>
#include<stack>
#include<queue>

#define NMAX 50005

using namespace std;

long n,m;
fstream fin,fout;

vector<list<long> > G;
long grad_interior[NMAX],vizitat[NMAX];
stack<long> varfuri_sortate;

void dfs(long x)
{

	vizitat[x]=1;

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

int main()
{
	long i,x,y;
	fin.open("sortaret.in",ios::in);
	fout.open("sortaret.out",ios::out);

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

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

	for(i=1;i<=n;i++)
		if(grad_interior[i]==0)
			dfs(i);

	while(!varfuri_sortate.empty())
	{
		fout<<varfuri_sortate.top()<<" ";
		varfuri_sortate.pop();
	}

	fout<<'\n';
	fout.close();
	fin.close();
	return 0;
}