test/graph/ebcc.test.cpp

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

Depends on

• src/graph/ebcc.hpp

Code

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

#include "../../src/graph/ebcc.hpp"

int main() {
  cin.tie(nullptr)->sync_with_stdio(false);
  int n, m;
  cin >> n >> m;
  EBCC ebcc(n);
  for (int _ = 0; _ < m; _++) {
    int u, v;
    cin >> u >> v;
    ebcc.adde(u, v);
  }
  int N = ebcc.work();
  vector<vector<int>> ebccvtx(N);
  for (int v = 0; v < n; v++) ebccvtx[ebcc.ebccid[v]].PUSHB(v);
  cout << N << "\n";
  for (int i = 0; i < N; i++) {
    assert(!ebccvtx[i].empty());
    cout << ebccvtx[i].size();
    for (int v : ebccvtx[i]) cout << " " << v;
    cout << "\n";
  }
  return 0;
}

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

#line 1 "src/graph/ebcc.hpp"
// 无向图的边双连通分量. 返回双联通分量个数, 点对应的连通分量编号在 `ebccid` 中.
struct EBCC {
  int n, m = 0, cur_dfn, cur_ebcc;
  vector<char> isbridge;
  vector<int> dfn, low, ebccid;
  vector<vector<pii>> G;
  EBCC(int n) : n(n), dfn(n, -1), low(n), ebccid(n, -1), G(n) {}
  void adde(int u, int v) { G[u].PUSHB({v, m}), G[v].PUSHB({u, m++}); }
  int work() {
    isbridge.assign(m, 0);
    for (int i = 0; i < n; i++)
      if (dfn[i] == -1) tarjan(i, -1);
    for (int i = 0; i < n; i++)
      if (ebccid[i] == -1) ebccid[i] = cur_ebcc++, dfs(i);
    return cur_ebcc;
  }

 private:
  void tarjan(int u, int fa_e) {
    dfn[u] = low[u] = cur_dfn++;
    for (const auto& [v, e] : G[u]) {
      if (dfn[v] == -1) {
        tarjan(v, e), low[u] = min(low[u], low[v]);
        if (low[v] > low[u]) isbridge[e] = 1;
      } else if (e != fa_e) {
        low[u] = min(low[u], dfn[v]);
      }
    }
  }
  void dfs(int u) {
    for (const auto& [v, e] : G[u]) {
      if (ebccid[v] != -1 || isbridge[e]) continue;
      ebccid[v] = ebccid[u], dfs(v);
    }
  }
};
#line 8 "test/graph/ebcc.test.cpp"

int main() {
  cin.tie(nullptr)->sync_with_stdio(false);
  int n, m;
  cin >> n >> m;
  EBCC ebcc(n);
  for (int _ = 0; _ < m; _++) {
    int u, v;
    cin >> u >> v;
    ebcc.adde(u, v);
  }
  int N = ebcc.work();
  vector<vector<int>> ebccvtx(N);
  for (int v = 0; v < n; v++) ebccvtx[ebcc.ebccid[v]].PUSHB(v);
  cout << N << "\n";
  for (int i = 0; i < N; i++) {
    assert(!ebccvtx[i].empty());
    cout << ebccvtx[i].size();
    for (int v : ebccvtx[i]) 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	5 ms	4 MB
g++	example_02	AC	4 ms	4 MB
g++	large_cycle_00	AC	45 ms	16 MB
g++	max_random_00	AC	110 ms	25 MB
g++	max_random_01	AC	112 ms	25 MB
g++	max_random_02	AC	121 ms	25 MB
g++	random_1_00	AC	85 ms	17 MB
g++	random_1_01	AC	75 ms	20 MB
g++	random_1_02	AC	43 ms	11 MB
g++	random_2_00	AC	23 ms	7 MB
g++	random_2_01	AC	9 ms	4 MB
g++	random_2_02	AC	31 ms	8 MB
g++	random_2_03	AC	42 ms	9 MB
g++	random_2_04	AC	19 ms	6 MB
g++	small_random_1_00	AC	5 ms	4 MB
g++	small_random_1_01	AC	4 ms	4 MB
g++	small_random_1_02	AC	4 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	5 ms	4 MB

Back to top page