Cod sursa(job #2157792)

Utilizator VladTiberiuMihailescu Vlad Tiberiu VladTiberiu Data 9 martie 2018 22:17:43
Problema Sortare topologica Scor 100
Compilator c Status done
Runda Arhiva educationala Marime 1.34 kb
#include <stdio.h>
#include <stdlib.h>

#define NMax 50003

typedef struct node{
    int value;
    struct node *next;
}Node;

Node *G[NMax];
int n,m,x,y,top;
int st[NMax],viz[NMax];

void insert(Node **first,int value){
    if(*first == NULL){
        Node *aux;
        aux = (Node *)malloc(1 * sizeof(Node));

        aux->value = value;
        aux->next = NULL;
        (*first) = aux;
        return;
    }
    Node *aux;
    aux = (Node *)malloc(1 * sizeof(int));

    aux->value = value;
    aux->next = (*first);
    (*first) = aux;
}
void print_list(Node *first){
    for(Node *p = first; p; p = p->next){
        printf("%d ",p->value);
    }
    printf("\n");
}

void dfs(int nod){
    viz[nod] = 1;

    for(Node *p = G[nod]; p; p = p->next){
        if(!viz[p->value]){
            dfs(p->value);
        }
    }

    st[++top] = nod;
}
int main(){
    freopen("sortaret.in","r",stdin);
    freopen("sortaret.out","w",stdout);

    scanf("%d%d",&n,&m);
    for(int i = 1; i <= n; ++i){
        G[i] = NULL;
    }

    for(int i = 1; i <= m; ++i){
        scanf("%d%d",&x,&y);
        insert(&G[x],y);
    }

    for(int i = 1; i <= n; ++i){
        if(!viz[i]){
            dfs(i);
        }
    }
    for(int i = n; i >= 1; --i){
        printf("%d ",st[i]);
    }
    return 0;
}