Cod sursa(job #2555506)

Utilizator Radu_FilipescuFilipescu Radu Radu_Filipescu Data 24 februarie 2020 09:23:13
Problema Sortare topologica Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.79 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];
deque <int> Q;
bool vis[NMAX];

void Read()
{
    fin >> N >> M;

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

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

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

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

      if( !vis[w] ) Dfs( w );
   }
   Q.push_back( nod );
}


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

    while( !Q.empty() ) {
        fout << Q.back() << ' ';
        Q.pop_back();
    }
}

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

    return 0;
}