Cod sursa(job #2919467)

Utilizator euyoTukanul euyo Data 17 august 2022 18:21:30
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.13 kb
#include <fstream>
#include <vector>
#include <algorithm>
 
using namespace std;
 
ifstream fin( "biconex.in" );
ofstream fout( "biconex.out" );
 
const int MAXN = 100005;
 
vector<int> G[MAXN];
vector<int> stk;
int dep[MAXN];
int _dep[MAXN];
 
vector<int> comps[MAXN];
int nc;
 
void del( int u ) {
  while ( stk.back() != u ) {
    comps[nc].push_back( stk.back() );
    stk.pop_back();
  }
  comps[nc].push_back(u);
  stk.pop_back();
}
 
void dfs( int u, int l ) {
  dep[u] = _dep[u] = l;
  stk.push_back( u );
  for ( auto v : G[u] ) {
    if ( dep[v] == 0 ) {
      dfs(v, l + 1);
      _dep[u] = min(_dep[u], _dep[v]);
      if ( _dep[v] >= dep[u] ) {
        del(v);
		comps[nc++].push_back(u);
      }
    } else {
      _dep[u] = min(_dep[u], dep[v]);
    }
  }
} 

int main() {
  int n, m, u, v;
 
  fin >> n >> m;
  while ( m-- ) {
    fin >> u >> v;
    G[u].push_back(v);
    G[v].push_back(u);
  }
  dfs(1, 1);
  fout << nc << "\n";
  for ( int c = 0; c < nc; ++c ) {
    sort(comps[c].begin(), comps[c].end());
    for ( auto x : comps[c] ) {
	  fout << x << " ";
    }
    fout << "\n";
  }
  fin.close();
  fout.close();
  return 0;
}