Cod sursa(job #296260)

Utilizator HaggisRanca Razvan Haggis Data 4 aprilie 2009 15:11:02
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.85 kb
#include<fstream>
using namespace std;
ifstream in("sortaret.in");
ofstream out("sortaret.out");
struct nod{int inf; nod*leg;}*p[50001],*u[50001];
int i,j,n,m,x,y,k,k1,b[50001],c[50001],t,f[50001],s[50001];

void dfsvisit(int r, int t)
{
	c[r]=1;
	s[r]=++t;
	nod*ti=p[r];
	while(ti && ti!=u[r]->leg)
		{
			if(!c[ti->inf])
				dfsvisit(ti->inf,t);
			ti=ti->leg;
		}
	c[r]=2;
	f[r]=++t;
	b[0]++;
	b[b[0]]=r;
}
int main ()
{
in>>n>>m;
for(i=1;i<=m;i++)
{
	in>>x>>y;
	int b1=0;
	nod*ti=p[x];
	while(ti && ti!=u[x])
		{
			if(ti->inf==y)
				b1=1;
			ti=ti->leg;
		}
	if(t && ti->inf==y)
		b1=1;
	if(!b1)
	{
	nod*nou=new nod;
	nou->inf=y;
	nou->leg=0;
	if(!p[x])
		p[x]=nou;
	else
		u[x]->leg=nou;
	u[x]=nou;
	}
}

for(i=1;i<=n;i++)
		if(!c[i])
			dfsvisit(i,t);
		
for(i=n;i>=1;i--)
	out<<b[i]<<" ";
return 0;
}