Cod sursa(job #2637019)

Utilizator andreic06Andrei Calota andreic06 Data 20 iulie 2020 22:04:03
Problema Sortare topologica Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.81 kb
#include <iostream>
#include <fstream>
#include <vector>

using namespace std;
const int N = 5e4;
const int M = 1e5;

bool visited[N+1];
vector<int> edges[N+1];
vector<int> res;

void dfs ( int start_node ) {
    visited[start_node] = 1;
    for ( int i = 0; i < (int)edges[start_node].size (); i ++ )
       if ( !visited[edges[start_node][i]] )
         dfs ( edges[start_node][i] );
    res.push_back ( start_node );
}

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

int main()
{
   int n, m;
   fin >> n >> m;

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

   for ( int i = 1; i <= n; i ++ )
      if ( !visited[i]  )
        dfs ( i );

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