Cod sursa(job #550418)

Utilizator irene_mFMI Irina Iancu irene_m Data 9 martie 2011 15:16:41
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.98 kb
#include <cstdio>
#define MaxN 50005
#define infile "sortaret.in"
#define outfile "sortaret.out"

struct edge{
      int x;
      edge *next;
}     *G[MaxN];

int uz[MaxN],sol[MaxN],N,M,nrsol;

void add(int x,int y)
{
      edge *q=new edge;
      q->x=y; q->next=G[x]; G[x]=q;
}

void read()
{
      int x,y;
      scanf("%d%d",&N,&M);
      for(;M;M--)
      {
            scanf("%d%d",&x,&y);
            add(x,y);
      }
}

void dfs(int nod)
{
      edge *q;
      uz[nod]=1;

      for(q=G[nod];q;q=q->next)
            if(!uz[q->x])
                  dfs(q->x);
      sol[++nrsol]=nod;
}

void write()
{
      int i;
      for(i=N;i>=1;i--)
            printf("%d ",sol[i]);
}

int main()
{
      freopen(infile,"r",stdin);
      freopen(outfile,"w",stdout);

      read();
      for(int i=1;i<=N;i++)
            if(!uz[i])
                  dfs(i);

      write();

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