Cod sursa(job #145778)

Utilizator Darth_NiculusIvan Nicolae Darth_Niculus Data 29 februarie 2008 14:45:59
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.96 kb
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define NMAX 50001
#define INPUT  "sortaret.in"
#define OUTPUT "sortaret.out"

int i,j,n,m,*G[NMAX],Gr[NMAX],St[NMAX],Mark[NMAX];

void DFS(int nod)
{
 int i;
 Mark[nod]=1;

 for (i=1;i<=G[nod][0];i++)
    if (!Mark[G[nod][i]])
      DFS(G[nod][i]);

 St[++St[0]]=nod;
}

int main()
{
 freopen(INPUT,"r",stdin);
 freopen(OUTPUT,"w",stdout);

 scanf("%d%d",&n,&m);
 for (i=1;i<=m;i++)
    {
     int x,y;
     scanf("%d%d",&x,&y);
     Gr[x]++;
    }

 fseek(stdin,0,SEEK_SET);

 for (i=1;i<=n;i++)
    {
     G[i]=(int*)malloc((Gr[i]+1)*sizeof(int));
     memset(G[i],0,sizeof(G[i]));
    }

 scanf("%d%d",&n,&m);
 for (i=1;i<=m;i++)
    {
     int x,y;
     scanf("%d%d",&x,&y);
     G[x][++G[x][0]]=y;
    }

 for (i=1;i<=n;i++)
    if (!Mark[i])
      DFS(i);

 for (i=St[0];i>=1;i--)
    printf("%d ",St[i]);

 fclose(stdin);
 fclose(stdout);
 return 0;
}