Cod sursa(job #2275373)

Utilizator MoldooooooooMoldoveanu Stefan Moldoooooooo Data 3 noiembrie 2018 09:49:18
Problema Sortare topologica Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.03 kb
#include <cstdio>
#include <cstdlib>
#define MaxN 50005
using namespace std;
int *A[MaxN], M, N, Order[MaxN], i, Grade[MaxN], T;
bool Use[MaxN];
void Read();
void DFS(int i);
void Write();
int main()
{
    freopen("sortaret.in", "r", stdin);
    freopen("sortaret.out", "w", stdout);
    Read();
    for(i=1; i<=N; ++i) if(!Grade[i]) {Use[i]=true; DFS(i);}
    Write();
    return 0;
}
void Read(){
    scanf("%d%d", &N, &M);
    for(i=1; i<=N; ++i){
        A[i]=(int *)realloc(A[i], sizeof(int));
        A[i][0]=0;
    }
    for(i=1; i<=M; ++i){
        int x, y;
        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;
        ++Grade[y];
    }
    return;
}
void DFS(int i){
    int j;
    for(j=1; j<=A[i][0]; ++j){
        if(Use[A[i][j]]==false){
            Use[A[i][j]]=true;
            DFS(A[i][j]);
        }
    }
    Order[++T]=i;
}
void Write(){
    for(i=T; i>=1; --i)printf("%d ", Order[i]);
    return;
}