Cod sursa(job #2940424)

Utilizator Fantastic_Mantudor voicu Fantastic_Man Data 15 noiembrie 2022 16:06:25
Problema Sortare topologica Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.77 kb
#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;
const int nmax = 50000;

ifstream fin ( "sortaret.in" );
ofstream fout ( "sortaret.out" );

vector < int > g[nmax + 1];
int vis[nmax + 1];
int in_deg[nmax + 1];
vector < int > ans;

void dfs ( int node ) {
    vis[node] = 1;
    for ( int x: g[node] )
        if ( !vis[x] )
            dfs ( x );
    ans.push_back ( node );
}

int main() {
    int n, m, p, x, y;
    fin >> n >> m;

    for ( int i = 1; i <= m; i++ ) {
        fin >> x >> y;
        g[x].push_back ( y );
        in_deg[y]++;
    }

    for ( int i = 1; i <= n; i++ )
        if ( in_deg[i] == 0 && !vis[i] )
            dfs ( i );

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

    for ( int x : ans )
        fout << x << ' ';


    return 0;
}