Cod sursa(job #2808412)

Utilizator andreic06Andrei Calota andreic06 Data 24 noiembrie 2021 23:54:56
Problema Componente tare conexe Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.49 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>

using namespace std;
const int NMAX = 1e5;

vector<int> graph[1 + NMAX];
bool visited[1 + NMAX]; bool on_stack[1 + NMAX];
int node_id[1 + NMAX]; int low_link[1 + NMAX];
stack<int> node_stack;

vector<int> scc[1 + NMAX];
int count_scc = 0;
int node_index = 1;
void dfs ( int root ) {
    visited[root] = true;
    node_id[root] = low_link[root] = node_index ++;
    node_stack.push ( root ); on_stack[root] = true;

    for ( auto node : graph[root] ) {
       if ( !visited[node] ) {
         dfs ( node );
         if ( on_stack[node] )
           low_link[root] = min ( low_link[root], low_link[node] );
       }
    }

    if ( node_id[root] == low_link[root] ) {
      count_scc ++;
      int curr_node;
      do {
        curr_node = node_stack.top ();
        scc[count_scc].push_back ( curr_node );
        on_stack[curr_node] = false;
        node_stack.pop ();
      }
      while ( curr_node != root );
    }

}


ifstream fin ( "ctc.in" );
ofstream fout ( "ctc.out" );
int main()
{
   int n, m; fin >> n >> m;
   for ( int i = 1; i <= m; i ++ ) {
      int u, v; fin >> u >> v;
      graph[u].push_back ( v );
   }

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

   fout << count_scc << "\n";
   for ( int i = 1; i <= count_scc; i ++ ) {
      for ( auto x : scc[i] )
         fout << x << " ";
      fout << "\n";
   }
    return 0;
}