Cod sursa(job #2866381)

Utilizator vladburacBurac Vlad vladburac Data 9 martie 2022 17:41:49
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.18 kb
#include <iostream>
#include <bits/stdc++.h>
#include <fstream>
using namespace std;
const int NMAX = 1e5;

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

stack <int> s;
vector <int> edges[NMAX+1];
vector <int> edges2[NMAX+1];
int viz[NMAX+1];

vector <int> components[NMAX+1];
int noComp = 0;

void dfs( int node ) {
  viz[node] = true;
  for( auto it: edges[node] ) {
    if( !viz[it] )
      dfs( it );
  }
  s.push( node );
}

void dfs2( int node ) {
  viz[node] = true;
  components[noComp].push_back( node );
  for( auto it: edges2[node] ) {
    if( !viz[it] )
      dfs2( it );
  }
}
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 );
    edges2[b].push_back( a );
  }
  for( i = 1; i <= n; i++ ) {
    if( !viz[i] )
      dfs( i );
  }
  for( i = 1; i <= n; i++ )
    viz[i] = false;
  while( !s.empty() ) {
    if( !viz[s.top()] ) {
      dfs2( s.top() );
      noComp++;
    }
    s.pop();
  }
  fout << noComp << "\n";
  for( i = 0; i < noComp; i++ ) {
    for( auto it: components[i] )
      fout << it << " ";
    fout << "\n";
  }
  return 0;
}