Cod sursa(job #3238001)

Utilizator tsg38Tsg Tsg tsg38 Data 15 iulie 2024 08:03:26
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.08 kb
#include <bits/stdc++.h>

using namespace std;
using ll = long long;

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

const int DIM = 1e5 + 1;

vector<int> G[DIM];
int tin[DIM], timer;
int low[DIM];

vector<vector<int>> bcc;
vector<int> stk;

void insert_bcc( int u, int v ) {
  vector<int> aux{u, v};
  while ( stk.back() != v ) {
	aux.push_back(stk.back());
	stk.pop_back();
  }
  stk.pop_back();
  bcc.push_back(aux);
}

void dfs( int u, int par = 0 ) {
  low[u] = tin[u] = ++timer;
  stk.push_back(u);
  for ( auto v : G[u] ) {
	if ( v == par ) continue;
	if ( !tin[v] ) { 
	  dfs(v, u);
      low[u] = min(low[u], low[v]);
	  if ( low[v] >= tin[u] ) {
	    insert_bcc(u, v);
	  }
	} else {
	  low[u] = min(low[u], tin[v]); 
	}
  }
}

int main() {
  ios_base::sync_with_stdio(0);
  fin.tie(0);
  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);
  fout << bcc.size() << "\n";
  for ( auto comp : bcc ) {
	for ( auto u : comp ) {
	  fout << u << " ";
	}
	fout << "\n";
  }
  fin.close();
  fout.close();
  return 0;
}