Cod sursa(job #2659478)

Utilizator Radu_FilipescuFilipescu Radu Radu_Filipescu Data 16 octombrie 2020 20:27:07
Problema Sortare topologica Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.8 kb
#include <bits/stdc++.h>

using namespace std;

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

const int NMAX = 50005;

int N, M;
vector <int> Ad[NMAX];
vector <int> stk;
bool vis[NMAX];

void Read()
{
    fin >> N >> M;
    for( int i = 1; i <= M; ++i ) {
        int a, b;

        fin >> a >> b;
        Ad[a].push_back( b );
    }
}

void TS( int nod ) {
    vis[nod] = true;

    int w;
    for( int i = 0; i < Ad[nod].size(); ++i ) {
        w = Ad[nod][i];

        if( !vis[w] ) TS( w );
    }

    stk.push_back( nod );
}

void Do()
{
    for( int i = 1; i <= N; ++i )
        if( !vis[i] ) TS( i );

    for( int i = stk.size() - 1; i >= 0; --i )
        fout << stk[i] << ' ';
}

int main()
{
    Read();
    Do();

    return 0;
}