Cod sursa(job #1207985)

Utilizator popalexPopescu Alexandru popalex Data 14 iulie 2014 14:00:29
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.8 kb
#include <stdio.h>
#include <vector>

#define NMAX 50001

int N, M;
bool viz[50001];
std::vector<int> vecini[NMAX], Q;
FILE *in, *out;

void dfs(int nod){

    if (viz[nod])   return;

    viz[nod] = true;
    for(int i = 0; i < vecini[nod].size(); i++){
        int y = vecini[nod][i];
        dfs(y);
    }
    Q.push_back(nod);
}


int main(){

    in = fopen("sortaret.in", "r");
    out = fopen("sortaret.out", "w");

    fscanf(in, "%d%d", &N, &M);
    std::fill(viz + 1, viz + N + 1, false);

    for(int i = 1; i <= M; i++){
        int x, y;
        fscanf(in, "%d%d", &x, &y);
        vecini[x].push_back(y);
    }

    for (int i = 1; i <= N; i++){
        dfs(i);
    }

    for(int i = Q.size() - 1; i >= 0; --i){
        fprintf(out, "%d ", Q[i]);
    }

    fclose(in);
    fclose(out);

    return 0;
}