Cod sursa(job #878378)

Utilizator FayedStratulat Alexandru Fayed Data 14 februarie 2013 13:50:27
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.01 kb
#include <cstdio>
#include <stdlib.h>
#define NMAX 50001
using namespace std;

int n,m;
int grad[NMAX];
int q[NMAX];
int * A[NMAX];

void read(){

    int x,y;
    freopen("sortaret.in","r",stdin);
    freopen("sortaret.out","w",stdout);
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++){

        A[i] = (int*)realloc(A[i],sizeof(int));
        A[i][0] = 0;
    }
    for(int i=1;i<=m;i++){

        scanf("%d%d",&x,&y);
        A[x][0]++;
        A[x] = (int*)realloc(A[x],(A[x][0]+1)*sizeof(int));
        A[x][A[x][0]] = y;
        grad[y]++;
    }
}

void solve(){

    int x;
    for(int i=1;i<=n;i++)
          if(!grad[i])
             q[++q[0]] = i;


    for(int i=1;i<=n;i++){
      x = q[i];

    for(int j=1;j<=A[x][0];j++){
         grad[A[x][j]]--;
            if(!grad[A[x][j]])
                q[++q[0]] = A[x][j];

    }
 }
}

void write(){

    for(int i=1;i<=n;i++)
        printf("%d ",q[i]);
}

int main(){

read();
solve();
write();
return 0;
}