Cod sursa(job #342754)

Utilizator marcelcodreaCodrea Marcel marcelcodrea Data 23 august 2009 13:30:03
Problema Sortare topologica Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.81 kb
#include<stdio.h>
struct Nod {
    int v;
    Nod *next;
};

Nod *a[50005];
int viz[50005];
int n;
int m;
int topo[50005];
int x;
int y;

void insert(Nod *&u, int val)
{
    Nod *k = new Nod;
    k->v = val;
    k->next = u;
    u = k;

}
int dfs(int s)
{
    viz[s] = 1;
    for(Nod *it = a[s]; it; it = it->next)
     if (!viz[it->v]) dfs(it->v);
    topo[++topo[0]] = s;
}

int main()
{
    freopen("sortaret.in","r",stdin);
    freopen("sortaret.out","w",stdout);

    scanf("%d %d",&n,&m);

    for(int i = 1; i <= m; i++)
     {
        scanf("%d %d",&x,&y);
        insert(a[x],y);
     }
    for(int i = 1; i <= n; i++)
     if (!viz[i])
     {
      dfs(i);
      for(int j = topo[0]; j > 0; j--)
       printf("%d ",topo[j]);
     topo[0] = 0;
     }
    return 0;
}