Cod sursa(job #2243746)

Utilizator borscalinCalin-Stefan Georgescu borscalin Data 21 septembrie 2018 12:01:30
Problema Sortare topologica Scor 0
Compilator c Status done
Runda Arhiva educationala Marime 1.36 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 bfs () {
    viz[stiva[st]] = 1;

    while ( st <= dr ) {
        int varf = stiva[st];
        int p = lst[varf];

        while ( p != 0 ) {
            int y = vf[p];

            if ( !viz[y] ) {
                stiva[++dr] = y, viz[y] = 1, succesori[y]--;
                if (succesori[y] == 0)
                    sol[++x] = y;
            }

            p = urm[p];
        }
        ++st;
    }
}

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 ) {
            sol[++x] = i;
            stiva[x] = i;
            ++dr;
            viz[i] = 1;
        }
    }

    bfs();

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

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

    fclose ( fout );

    return 0;
}