test/graph/vbcc.test.cpp

• View this file on GitHub
• Last update: 2025-10-26 10:54:48+08:00
• Problem: https://judge.yosupo.jp/problem/biconnected_components

Depends on

• src/graph/vbcc.hpp
• src/misc/read.hpp

Code

// competitive-verifier: PROBLEM https://judge.yosupo.jp/problem/biconnected_components
#include <bits/stdc++.h>
#define PUSHB push_back
using namespace std;
using pii = pair<int, int>;
using ll = long long;

#include "../../src/graph/vbcc.hpp"
#include "../../src/misc/read.hpp"

int main() {
  cin.tie(nullptr)->sync_with_stdio(false);
  int n = read(), m = read();
  using ll = long long;
  VBCC vbcc(n);
  for (int _ = 0; _ < m; _++) {
    int u = read(), v = read();
    vbcc.adde(u, v);
  }
  int N = vbcc.work();
  cout << N << "\n";
  for (int i = 0; i < N; i++) {
    const auto& arr = vbcc.vbccs[i];
    assert(!arr.empty());
    cout << arr.size();
    for (int v : arr) cout << " " << v;
    cout << "\n";
  }
  return 0;
}

#line 1 "test/graph/vbcc.test.cpp"
// competitive-verifier: PROBLEM https://judge.yosupo.jp/problem/biconnected_components
#include <bits/stdc++.h>
#define PUSHB push_back
using namespace std;
using pii = pair<int, int>;
using ll = long long;

#line 1 "src/graph/vbcc.hpp"
// 无向图的点双连通分量. 返回双联通分量个数, 点对应的连通分量在 `vbccs` 中.
struct VBCC {
  int n, m = 0, cur_dfn;
  vector<char> iscut;
  stack<int> stk;
  vector<int> dfn, low;
  vector<vector<int>> vbccs;
  vector<vector<pii>> G;
  VBCC(int n) : n(n), iscut(n), dfn(n, -1), low(n), G(n) {}
  void adde(int u, int v) { G[u].PUSHB({v, m}), G[v].PUSHB({u, m++}); }
  int work() {
    for (int i = 0; i < n; i++)
      if (dfn[i] == -1) tarjan(i, -1), stk.pop();
    assert(stk.empty());
    return vbccs.size();
  }

 private:
  void tarjan(int u, int fa_e) {
    dfn[u] = low[u] = cur_dfn++, stk.push(u);
    int sons = 0, flag = 0, tmp;
    for (const auto& [v, e] : G[u]) {
      if (dfn[v] == -1) {
        tarjan(v, e), sons++, low[u] = min(low[u], low[v]);
        if (low[v] >= dfn[u]) {
          flag++, vbccs.PUSHB({});
          if (fa_e != -1 || flag > 1) iscut[u] = 1;
          do {
            tmp = stk.top(), stk.pop(), vbccs.rbegin()->PUSHB(tmp);
          } while (tmp != v);
          vbccs.rbegin()->PUSHB(u);
        }
      } else if (e != fa_e) {
        low[u] = min(low[u], dfn[v]);
      }
    }
    if (fa_e == -1 && sons == 0) vbccs.PUSHB({u});
  }
};
#line 1 "src/misc/read.hpp"
#define GC ch = getchar_unlocked()
ll read() {
  ll x = 0, f = 1, GC;
  while (ch < '0' || ch > '9') ch == '-' ? f = -1, GC : GC;
  while (ch >= '0' && ch <= '9') x = x * 10 + ch - '0', GC;
  return x * f;
}
#undef GC
#line 10 "test/graph/vbcc.test.cpp"

int main() {
  cin.tie(nullptr)->sync_with_stdio(false);
  int n = read(), m = read();
  using ll = long long;
  VBCC vbcc(n);
  for (int _ = 0; _ < m; _++) {
    int u = read(), v = read();
    vbcc.adde(u, v);
  }
  int N = vbcc.work();
  cout << N << "\n";
  for (int i = 0; i < N; i++) {
    const auto& arr = vbcc.vbccs[i];
    assert(!arr.empty());
    cout << arr.size();
    for (int v : arr) cout << " " << v;
    cout << "\n";
  }
  return 0;
}

Test cases

Env	Name	Status	Elapsed	Memory
g++	example_00	AC	5 ms	4 MB
g++	example_01	AC	4 ms	4 MB
g++	example_02	AC	4 ms	4 MB
g++	large_cycle_00	AC	345 ms	115 MB
g++	max_line_clique_00	AC	154 ms	67 MB
g++	max_random_00	AC	342 ms	72 MB
g++	max_random_2_00	AC	341 ms	53 MB
g++	max_random_2_01	AC	306 ms	53 MB
g++	max_random_2_02	AC	298 ms	53 MB
g++	max_star_00	AC	231 ms	66 MB
g++	max_tree_00	AC	327 ms	66 MB
g++	min_00	AC	5 ms	4 MB
g++	min_01	AC	6 ms	4 MB
g++	min_02	AC	5 ms	4 MB
g++	random_1_00	AC	247 ms	60 MB
g++	random_2_00	AC	255 ms	47 MB
g++	random_2_01	AC	139 ms	49 MB
g++	random_2_02	AC	79 ms	25 MB
g++	small_random_1_00	AC	5 ms	4 MB
g++	small_random_2_00	AC	4 ms	4 MB
g++	small_random_2_01	AC	4 ms	4 MB
g++	small_random_2_02	AC	4 ms	4 MB

Back to top page