Cod sursa(job #2243770)

Utilizator borscalinCalin-Stefan Georgescu borscalin Data 21 septembrie 2018 12:40:39
Problema Sortare topologica Scor 100
Compilator c Status done
Runda Arhiva educationala Marime 1.06 kb
#include <stdio.h>
#include <stdlib.h>
#define NMAX 50000
#define MMAX 100000

int n, m, p, nr, vf[1 + 2 * MMAX], urm[1 + 2 * MMAX], lst[1 + NMAX], viz[1 + NMAX], s, x, succesori[1 + NMAX];
int st, dr;
int stiva[1 + NMAX];
int sol[1 + NMAX];

void adauga ( int x, int y ) {
    ++nr;
    vf[nr] = y;
    urm[nr] = lst[x];
    lst[x] = nr;
}

void dfs ( int node ) {
    viz[node] = 1;
    int p = lst[node];
    while ( p != 0 ) {
        int y = vf[p];

        if ( !viz[y] )
            dfs ( y );

        p = urm[p];
    }

    sol[++x] = node;
}

int main() {
    FILE *fin = fopen ( "sortaret.in", "r" );
    fscanf ( fin, "%d%d", &n, &m );
    int i;

    for ( i = 1; i <= m; ++i ) {
        int x, y;
        fscanf ( fin, "%d%d", &x, &y );
        adauga ( x, y );
        ++succesori[y];
    }

    fclose ( fin );

    st = 1;

    for ( i = 1; i <= n; ++i )
        if ( succesori[i] == 0 )
            dfs(i);

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

    for ( i = n; i >= 1; --i )
        fprintf ( fout, "%d ", sol[i] );

    fclose ( fout );

    return 0;
}