Cod sursa(job #470350)

Utilizator IrnukIrina Grosu Irnuk Data 13 iulie 2010 13:46:56
Problema Sortare topologica Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.06 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];
queue<long> varfuri_sortate;

void dfs(long x)
{
	stack<long> S;

	S.push(x);
	vizitat[x]=1;

	while(!S.empty())
	{
		x=S.top();
		S.pop();
		varfuri_sortate.push(x);
		list<long>::iterator itr;
		for(itr=G[x].begin(); itr!=G[x].end(); itr++)
			if(vizitat[*itr]==0)
			{
				vizitat[*itr]=1;
				S.push(*itr);
			}
	}
}

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.front()<<" ";
		varfuri_sortate.pop();
	}

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