Cod sursa(job #2943071)

Utilizator teodorescunicolasteodorescu nicolas alexandru teodorescunicolas Data 20 noiembrie 2022 15:55:50
Problema Sortare topologica Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.96 kb
#include <stdio.h>
#include <algorithm>
#include <vector>

#define NMAXX 50000
#define MMAXX 100000

using namespace std;

vector <int> topologic;
vector <int> graph[NMAXX];
int marked[NMAXX];

void dfs( int node ) {
    marked[node] = true;

    for ( int neighbour : graph[node] )
        if ( !marked[neighbour] )
            dfs( neighbour );

    topologic.push_back( node );
}

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

    fin = fopen( "sortaret.in", "r" );
    fout = fopen( "sortaret.out", "w" );

    fscanf( fin, "%d%d", &n, &m );
    for ( i = 0; i < m; i++ ) {
        fscanf( fin, "%d%d", &x, &y );
        graph[x - 1].push_back( y - 1 );
    }

    for ( i = 0; i < n; i++ )
        if ( !marked[i] )
            dfs( i );

    reverse( topologic.begin(), topologic.end() );

    for ( int node : topologic )
        fprintf( fout, "%d ", node );

    fclose( fin );
    fclose( fout );
    return 0;
}