Cod sursa(job #3123746)

Utilizator vladburacBurac Vlad vladburac Data 25 aprilie 2023 10:45:34
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.42 kb
#include <bits/stdc++.h>
using namespace std;
const int NMAX = 1e5;

// tarjan for SCCs

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

vector <int> edges[NMAX+1];
bool viz[NMAX+1];
stack <int> stiva;
bool inStack[NMAX+1];
int desc[NMAX+1], low[NMAX+1];
int timp;
vector<int> comps[NMAX+1];
int k;

void dfs( int node ) {
  viz[node] = true;
  desc[node] = low[node] = timp++;
  stiva.push( node );
  inStack[node] = true;
  for( auto vec: edges[node] ) {
    if( !viz[vec] ) {
      dfs( vec );
      low[node] = min( low[node], low[vec] );
    }
    else if( inStack[vec] )
      low[node] = min( low[node], desc[vec] );
  }
  if( low[node] == desc[node] ) { // head, the reason it works is that we deal with all the lower nodes first
    // so everything under node is already processed
    while( stiva.top() != node ) {
      comps[k].push_back( stiva.top() );
      inStack[stiva.top()] = false;
      stiva.pop();
    }
    comps[k].push_back( stiva.top() );
    inStack[stiva.top()] = false;
    stiva.pop();
    k++;
  }
}

int main() {
  int n, m, i, a, b;
  fin >> n >> m;
  for( i = 0; i < m; i++ ) {
    fin >> a >> b;
    edges[a].push_back( b );
  }
  k = 0;
  for( i = 1; i <= n; i++ ) {
    if( !viz[i] )
      dfs( i );
  }
  fout << k << "\n";
  for( i = 0; i < k; i++ ) {
    for( auto x: comps[i] )
      fout << x << " ";
    fout << "\n";
  }
  return 0;
}