Cod sursa(job #1739240)

Utilizator dodecagondode cagon dodecagon Data 8 august 2016 23:25:39
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.65 kb
#include <stdio.h>
#include <stdlib.h>

struct list 
{
	int x;
	list * next;
} ;

int n,m,k,a[50009],x,y,i;
list * g[50009],* p;
char u[50009];


void dfs(int v)
{
	u[v]=1;

	for (list * p = g[v]; p ; p=p->next)
	  if (!u[p->x])
	  	dfs(p->x);

	 a[k++]=v; 
}

int main()
{

  FILE * in = fopen("sortaret.in","r");
  FILE * out = fopen("sortaret.out","w");


   fscanf(in,"%d%d",&n,&m);

   for (i=0;i<m;++i)
   {
   	fscanf(in,"%d%d",&x,&y);
    p=(list *) malloc(sizeof(list));
    p->next=g[x];
    p->x=y;
    g[x]=p;
   }

  for (i=1;i<=n;++i)
  	if (!u[i])
  		dfs(i);

  	for (i=k-1;i>=0;--i)
  		fprintf(out,"%d ",a[i]);
  	fclose(in); fclose(out);

	return 0;
}