Cod sursa(job #2690823)

Utilizator retrogradLucian Bicsi retrograd Data 26 decembrie 2020 02:55:41
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.31 kb
#include <bits/stdc++.h>

using namespace std;

template<typename Graph, typename CB>
void BCC(Graph& graph, CB cb) {
  int timer = 0, n = graph.size();
  vector<int> enter(n, -1), stk, comp;

  function<int(int, int)> dfs = [&](int node, int par) {
    enter[node] = timer++;
    int ret = enter[node];
    stk.push_back(node);

    for (auto vec : graph[node]) {
      if (vec == par) continue;
      if (enter[vec] != -1) {
        ret = min(ret, enter[vec]);
      } else {
        int sz = stk.size(), low = dfs(vec, node);
        ret = min(ret, low);
        if (low >= enter[node]) {
          stk.push_back(node);
          comp = {stk.begin() + sz, stk.end()}; 
          cb(comp); stk.resize(sz);
        }
      }
    }
    return ret;
  };
  for (int i = 0; i < n; ++i)
    if (enter[i] == -1) 
      dfs(i, -1);
}


int main() {
  ifstream cin("biconex.in");
  ofstream cout("biconex.out");
  int n, m; cin >> n >> m;
  vector<vector<int>> graph(n);
  for (int i = 0; i < m; ++i) {
    int a, b; cin >> a >> b; --a; --b;
    graph[a].push_back(b);
    graph[b].push_back(a);
  }
  vector<vector<int>> comps;
  BCC(graph, [&](vector<int> comp) {
    comps.push_back(comp);
  });
  cout << comps.size() << '\n';
  for (auto comp : comps) {
    for (auto x : comp) 
      cout << x + 1 << " ";
    cout << '\n';
  }
  return 0;
}