Cod sursa(job #529903)

Utilizator marcelcodreaCodrea Marcel marcelcodrea Data 6 februarie 2011 14:54:25
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.79 kb
#include <stdio.h>

int n,m;
struct Nod {
    int v;
    Nod* next;
};

using namespace std;

Nod* a[50001];
char viz[50001];
int sortt[50005];
int x,y;

void add(Nod *&p, int val) {
    Nod* k = new Nod();
    k->v = val;
    k->next = p;
    p = k;
}

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

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

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