Cod sursa(job #2770686)

Utilizator LucaMihaiLM10Luca Ilie LucaMihaiLM10 Data 22 august 2021 17:25:49
Problema Sortare topologica Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.04 kb
#include <stdio.h>
#include <vector>

#define MAX_N 50000

using namespace std;

int mare[MAX_N], q[MAX_N];
vector <int> edge[MAX_N];

int main() {
    FILE *fin, *fout;
    int n, m, a, b, first, last, p, i, j;

    fin = fopen( "sortaret.in", "r" );
    fscanf( fin, "%d%d", &n, &m );
    for ( i = 0; i < m; i++ ) {
        fscanf( fin, "%d%d", &a, &b );
        a--;
        b--;
        edge[a].push_back( b );
        mare[b]++;
    }
    fclose( fin );

    first = 0;
    last = -1;
    for ( i = 0; i < n; i++ ) {
        if ( mare[i] == 0 ) {
            last++;
            q[last] = i;
        }
    }
    fout = fopen( "sortaret.out", "w" );
    for ( i = 0; i < n; i++ ) {
        p = q[first];
        first++;
        fprintf( fout, "%d ", p + 1 );
        for ( j = 0; j < edge[p].size(); j++ ) {
            mare[edge[p][j]]--;
            if ( mare[edge[p][j]] == 0 ) {
                last++;
                q[last] = edge[p][j];
            }
        }
    }
    fclose( fout );

    return 0;
}