Cod sursa(job #1405265)

Utilizator Master011Dragos Martac Master011 Data 28 martie 2015 23:33:22
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.91 kb
#include<cstdio>
using namespace std;

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

const int nMax = 50000, lMax = 100000;
int val[lMax], urm[lMax], lst[nMax], sol[nMax], cnt, n, m;
int viz[nMax];

void dfs(int nod){
    viz[nod] = 1;
    int poz = lst[nod];
    while(poz != -1){
        if(!viz[val[poz]])
            dfs(val[poz]);
        poz = urm[poz];
    }

    sol[cnt++] = nod;
}

int main (){
    fscanf(in,"%d%d",&n,&m);

    for(int i = 0 ; i < m ; i++) lst[i] = -1;

    int x,y;
    for(int i = 0 ; i < m ; i++){
        fscanf(in,"%d%d",&x,&y);

        val[i] = y - 1;
        urm[i] = lst[x - 1];
        lst[x - 1] = i;
    }

    for(int i = 0 ; i < n ; i++){
        if(!viz[i])
            dfs(i);
    }

    for(int i = n - 1 ; i >= 0 ; i--){
        fprintf(out,"%d ", sol[i] + 1);
    }

    fprintf(out,"\n");
    return 0;
}