Cod sursa(job #667566)

Utilizator galbenugalbenu dorin galbenu Data 23 ianuarie 2012 13:12:07
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.87 kb
#include<fstream>
#define mmax 100010
#define nmax 50005
using namespace std;
ifstream f("sortaret.in",fstream::in);
ofstream g("sortaret.out",fstream::out);
struct nod
{unsigned short int inf; 
 nod *urm;
};
nod * L[nmax];
unsigned short int sol[nmax],n,x,y;
unsigned int m,i;
bool viz[nmax];
void add(unsigned int x,unsigned int y)
{nod *nou;
 nou=new nod; 
 nou->inf=x;
 nou->urm=L[y];
 L[y]=nou;
}
void read()
{unsigned int i;  
 f>>n>>m;
  for(i=1;i<=m;i++)
	  f>>x>>y,add(x,y);
}
void DF(unsigned int x)
{nod *p;
 viz[x]=1; 
  for(p=L[x];p;p=p->urm)
	   if(!viz[p->inf])
		    DF(p->inf);
sol[++sol[0]]=x;
}
void solve()
{unsigned int i; 
 for(i=1;i<=n;i++)
	  if(!viz[i])
		DF(i);
}
void show()
{unsigned int i;
 for(i=1;i<=sol[0];i++)
	 g<<sol[i]<<" ";
}
int main()
{read();
 solve();
 show();
 f.close();
 g.close();
 return 0;
}