Cod sursa(job #527033)

Utilizator maooBompa Mario maoo Data 30 ianuarie 2011 14:46:56
Problema Sortare topologica Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.76 kb
#include<cstdio>
#include<vector>

using namespace std;
vector<int> v[50001];
vector<int> g;
int n,m,x,y,i,state[50001];
void read(),solve(),df(int k),show();
int main()
{
	read();
	solve();
	show();
}
void read()
{
	freopen("sortaret.in","r",stdin);
	freopen("sortaret.out","w",stdout);
	scanf("%d %d",&n,&m);
	for(;m;m--)
	{
		scanf("%d%d",&x,&y);v[x].push_back(y);
	}
}
void solve()
{
	for(i=1;i<=n;i++)
		if(!state[n])
			df(i);
}
void df(int nod)
{
	vector<int>::reverse_iterator it;
	state[nod]=1;
	for(it=v[nod].rbegin();it!=v[nod].rend();it++)
		if(!state[*it])
			df(*it);
	state[nod]=2;
	g.push_back(nod);
}
void show()
{
	
	vector<int>::reverse_iterator it;
	for(it=g.rbegin();it!=g.rend();it++)
		printf("%d ",*it);
}