Cod sursa(job #2947889)

Utilizator Victor2006Nicola Victor-Teodor Victor2006 Data 26 noiembrie 2022 20:44:50
Problema Sortare topologica Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.11 kb
#include <stdio.h>
#include <vector>
#include <queue>
#define N 50000

std::queue <int> q;
std::vector <int> g[1 + N], ans;
int inDeg[1 + N];
int n;

void sortareTopologica() {
    int qfront;
    for ( int i = 1; i <= n; i ++ )
        if ( inDeg[i] == 0 )
            q.push( i );
    while ( !q.empty() ) {
        qfront = q.front();
        q.pop();
        ans.push_back( qfront );

        for ( unsigned int i = 0; i < g[qfront].size(); i ++ ) {
            inDeg[g[qfront][i]] --;
            if ( inDeg[g[qfront][i]] == 0 )
                q.push( g[qfront][i] );
        }
    }
}

int main() {
    FILE *fin, *fout;
    int m, x, y;

    fin = fopen( "sortaret.in", "r" );
    fscanf( fin, "%d%d", &n, &m );
    for ( int i = 0; i < m; i ++ ) {
        fscanf( fin, "%d%d", &x, &y );
        g[x].push_back( y );
        inDeg[y] ++;
    }
    fclose( fin );

    sortareTopologica();

    fout = fopen( "sortaret.out", "w" );
    for ( int i = 0; i < ans.size(); i ++ )
        fprintf( fout, "%d ", ans[i] );
    fprintf( fout, "\n" );
    fclose( fout );
    return 0;
}