Cod sursa(job #206589)

Utilizator mika17Mihai Alex Ionescu mika17 Data 7 septembrie 2008 21:36:58
Problema Sortare topologica Scor 20
Compilator cpp Status done
Runda Arhiva educationala Marime 1.25 kb
#include <stdio.h>
#include <stdlib.h>

int N,M;
int * A[50001];
bool vis[50001];
struct rec {int node; rec * next;} *fi, *la, *st, *dr;

void citire()
{
    freopen("sortaret.in","r",stdin);
    scanf("%d %d",&N,&M);

    for(int i = 1 ; i <= N; ++i)
    {
       A[i] = (int*) malloc(sizeof(int));
       A[i][0] = 0;
    }

    for(int i = 0 ; i < M; ++i)
    {
     int u,v;
     scanf("%d %d",&u,&v);

     A[u][0] ++;

     A[u] = (int*) realloc(A[u], (A[u][0] + 1) * sizeof(int));

     A[u][A[u][0]] = v;
    }
}

void add(int key,rec * & l,rec * & r)
{
 if(!l)
   {
    r = l = (rec*) malloc(sizeof (rec));
    l->node = key;
    l->next = 0;
   }
  else
   {
    r = r->next = (rec*) malloc(sizeof (rec));
    r->node = key;
    r->next = 0;
   }
}

void dfs(int i)
{
 vis[i] = 1;
 add(i,st,dr);
 for(int j = 1; j <= A[i][0]; ++j)
   if(!vis[A[i][j]])
    dfs(A[i][j]);
}

void tsort()
{
 for(int i = 1; i <= N; ++i)
    if(!vis[i])
    {
      dfs(i);
      dr->next = fi;
      fi = st;
      if(!la) la = dr;
      st = dr = 0;
    }
 freopen("sortaret.out","w",stdout);
 for(rec * p = fi ; p != 0 ; p = p -> next)
   printf("%d ",p->node);

}

int main()
{
 citire();
 tsort();
 return 0;
}