Cod sursa(job #2637018)

Utilizator andreic06Andrei Calota andreic06 Data 20 iulie 2020 22:03:17
Problema Sortare topologica Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.91 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;
int into[N+1];

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]] ) {
         into[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 );
      into[y] ++;
   }

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

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