Cod sursa(job #412112)

Utilizator cezyGrigore Cezar cezy Data 5 martie 2010 12:54:02
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.67 kb
#include<fstream>
#include<vector>
using namespace std;
#define nmax 50005
vector<int> g[nmax];
int postord[nmax],viz[nmax];
int n,m,k;
void citire ()
{
	ifstream fin("sortaret.in");
	fin>>n>>m;
	int i,a,b;
	for(i=1;i<=m;i++)
		fin>>a>>b,g[a].push_back(b);
	fin.close ();
}
void dfs_sort(int nod)
{
	viz[nod]=1;
	int i;
	for(i=0;i<g[nod].size();i++)
		if(!viz[g[nod][i]])
			dfs_sort(g[nod][i]);
	postord[++k]=nod;
}
void scrie ()
{
	int i;
	ofstream fout("sortaret.out");
	for(i=n;i>=1;i--)
		fout<<postord[i]<<' ';
	fout.close();
}
int main ()
{
	citire ();
	int i;
	for(i=1;i<=n;i++)
		if(!viz[i])
		 dfs_sort(i);
	scrie ();
	return 0;
}