Cod sursa(job #372550)

Utilizator bora_marianBora marian bora_marian Data 10 decembrie 2009 19:17:41
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.74 kb
#include<fstream>
using namespace std;
void read();
struct nod{
  int info;
  nod *next;
};
int n,m,vizitat[50003],ordine[50003],timp;
nod *a[50003];
ofstream fout("sortaret.out");
void dfs(int x){
	vizitat[x]=1;
	for(nod *p=a[x] ; p ;p=p->next)
		if(vizitat[p->info]==0)
		   dfs(p->info);
	timp++;
	ordine[timp]=x;
}
int main()
{
	read();
	for(int i=1;i<=n;i++)
		if(vizitat[i]==0)
		   dfs(i);

	for(int i=n ;  i; --i)
			fout<<ordine[i]<<" ";
	return 0;
}

void read()
{
  ifstream fin("sortaret.in");
   int m;
   fin>>n>>m;
   for(int i=1;i<=n;i++)
     a[i]=NULL;
   for(;m;m--)
    {
     int i,j;
     fin>>i>>j;
     nod*p;
     p=new nod;
     p->info=j;
     p->next=a[i];
     a[i]=p;
    }
}