library
This documentation is automatically generated by online-judge-tools/verification-helper
test/unit/lowlink.test.cpp
- View this file on GitHub
- Last update: 2026-10-25 23:38:54+09:00
- Problem: http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ITP1_1_A
Depends on
Code
#define PROBLEM "http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ITP1_1_A"
#include <cassert>
#include <iostream>
#include <random>
#include <utility>
#include <vector>
#include "graph/lowlink.hpp"
// number of connected components after removing vertex `skip_v` and edge `skip_e`
int components(int n, const std::vector<std::pair<int, int>>& edges, int skip_v, int skip_e) {
std::vector<std::vector<int>> g(n);
for (int e = 0; e < int(edges.size()); e++) {
if (e == skip_e) continue;
auto [u, v] = edges[e];
if (u == skip_v || v == skip_v) continue;
g[u].push_back(v);
g[v].push_back(u);
}
std::vector<bool> seen(n, false);
int res = 0;
for (int r = 0; r < n; r++) {
if (r == skip_v || seen[r]) continue;
res++;
std::vector<int> st = {r};
seen[r] = true;
while (!st.empty()) {
int v = st.back();
st.pop_back();
for (int u : g[v]) {
if (!seen[u]) seen[u] = true, st.push_back(u);
}
}
}
return res;
}
int main() {
std::mt19937 rng(777);
for (int it = 0; it < 500; it++) {
int n = 1 + rng() % 9;
int m = rng() % 14;
std::vector<std::pair<int, int>> edges(m);
for (auto& [u, v] : edges) u = rng() % n, v = rng() % n; // multi-edges and self-loops
lowlink g(n);
for (int e = 0; e < m; e++) assert(g.add_edge(edges[e].first, edges[e].second) == e);
g.build();
int base = components(n, edges, -1, -1);
std::vector<int> br, ap;
for (int e = 0; e < m; e++) {
bool b = components(n, edges, -1, e) > base;
assert(g.is_bridge(e) == b);
if (b) br.push_back(e);
}
assert(g.bridges() == br);
for (int v = 0; v < n; v++) {
// removing v also removes v itself from the count
bool a = components(n, edges, v, -1) > base;
assert(g.is_articulation(v) == a);
if (a) ap.push_back(v);
}
assert(g.articulation_points() == ap);
// same 2-edge-connected component <=> connected after removing any single edge
auto groups = g.two_edge_connected_components();
std::vector<int> cnt(groups.size(), 0);
for (int c = 0; c < int(groups.size()); c++) {
for (int v : groups[c]) assert(g.component(v) == c), cnt[c]++;
}
int total = 0;
for (int x : cnt) assert(x > 0), total += x;
assert(total == n);
for (int u = 0; u < n; u++) {
for (int v = u + 1; v < n; v++) {
bool same = true;
// connected in the graph without bridges?
std::vector<std::pair<int, int>> nb;
for (int e = 0; e < m; e++) if (!g.is_bridge(e)) nb.push_back(edges[e]);
std::vector<std::vector<int>> h(n);
for (auto [a, b] : nb) h[a].push_back(b), h[b].push_back(a);
std::vector<bool> seen(n, false);
std::vector<int> st = {u};
seen[u] = true;
while (!st.empty()) {
int x = st.back();
st.pop_back();
for (int y : h[x]) if (!seen[y]) seen[y] = true, st.push_back(y);
}
same = seen[v];
assert((g.component(u) == g.component(v)) == same);
}
}
}
// long path: no recursion, so n = 200000 must not overflow the stack
{
int n = 200000;
lowlink g(n);
for (int i = 0; i + 1 < n; i++) g.add_edge(i, i + 1);
g.build();
assert(int(g.bridges().size()) == n - 1);
assert(int(g.articulation_points().size()) == n - 2);
assert(g.two_edge_connected_components().size() == size_t(n));
}
std::cout << "Hello World" << std::endl;
return 0;
}#line 1 "test/unit/lowlink.test.cpp"
#define PROBLEM "http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ITP1_1_A"
#include <cassert>
#include <iostream>
#include <random>
#include <utility>
#include <vector>
#line 2 "graph/lowlink.hpp"
#include <algorithm>
#line 6 "graph/lowlink.hpp"
struct lowlink {
public:
lowlink() : lowlink(0) {
}
explicit lowlink(int n) : _n(n), g(n), ord(n, -1), low(n), comp(n, -1), art(n, false) {
}
int add_edge(int u, int v) {
assert(0 <= u && u < _n);
assert(0 <= v && v < _n);
int e = int(edges.size());
edges.emplace_back(u, v);
g[u].emplace_back(v, e);
g[v].emplace_back(u, e);
return e;
}
void build() {
int m = int(edges.size());
bridge.assign(m, false);
std::vector<int> it(_n, 0), par_edge(_n, -1), children(_n, 0);
int t = 0;
for (int r = 0; r < _n; r++) {
if (ord[r] != -1) continue;
std::vector<int> st = {r};
ord[r] = low[r] = t++;
while (!st.empty()) {
int v = st.back();
if (it[v] < int(g[v].size())) {
auto [u, e] = g[v][it[v]++];
if (e == par_edge[v]) continue;
if (ord[u] == -1) {
ord[u] = low[u] = t++;
par_edge[u] = e;
children[v]++;
st.push_back(u);
} else {
low[v] = std::min(low[v], ord[u]);
}
} else {
st.pop_back();
if (st.empty()) continue;
int p = st.back();
low[p] = std::min(low[p], low[v]);
if (low[v] > ord[p]) bridge[par_edge[v]] = true;
if (low[v] >= ord[p] && p != r) art[p] = true;
}
}
art[r] = children[r] >= 2;
}
_num_components = 0;
for (int r = 0; r < _n; r++) {
if (comp[r] != -1) continue;
comp[r] = _num_components;
std::vector<int> st = {r};
while (!st.empty()) {
int v = st.back();
st.pop_back();
for (auto [u, e] : g[v]) {
if (bridge[e] || comp[u] != -1) continue;
comp[u] = _num_components;
st.push_back(u);
}
}
_num_components++;
}
}
bool is_bridge(int e) const {
assert(0 <= e && e < int(edges.size()));
return bridge[e];
}
bool is_articulation(int v) const {
assert(0 <= v && v < _n);
return art[v];
}
std::vector<int> bridges() const {
std::vector<int> res;
for (int e = 0; e < int(edges.size()); e++) {
if (bridge[e]) res.push_back(e);
}
return res;
}
std::vector<int> articulation_points() const {
std::vector<int> res;
for (int v = 0; v < _n; v++) {
if (art[v]) res.push_back(v);
}
return res;
}
int component(int v) const {
assert(0 <= v && v < _n);
return comp[v];
}
std::vector<std::vector<int>> two_edge_connected_components() const {
std::vector<std::vector<int>> res(_num_components);
for (int v = 0; v < _n; v++) res[comp[v]].push_back(v);
return res;
}
private:
int _n, _num_components = 0;
std::vector<std::vector<std::pair<int, int>>> g;
std::vector<std::pair<int, int>> edges;
std::vector<int> ord, low, comp;
std::vector<bool> art, bridge;
};
#line 9 "test/unit/lowlink.test.cpp"
// number of connected components after removing vertex `skip_v` and edge `skip_e`
int components(int n, const std::vector<std::pair<int, int>>& edges, int skip_v, int skip_e) {
std::vector<std::vector<int>> g(n);
for (int e = 0; e < int(edges.size()); e++) {
if (e == skip_e) continue;
auto [u, v] = edges[e];
if (u == skip_v || v == skip_v) continue;
g[u].push_back(v);
g[v].push_back(u);
}
std::vector<bool> seen(n, false);
int res = 0;
for (int r = 0; r < n; r++) {
if (r == skip_v || seen[r]) continue;
res++;
std::vector<int> st = {r};
seen[r] = true;
while (!st.empty()) {
int v = st.back();
st.pop_back();
for (int u : g[v]) {
if (!seen[u]) seen[u] = true, st.push_back(u);
}
}
}
return res;
}
int main() {
std::mt19937 rng(777);
for (int it = 0; it < 500; it++) {
int n = 1 + rng() % 9;
int m = rng() % 14;
std::vector<std::pair<int, int>> edges(m);
for (auto& [u, v] : edges) u = rng() % n, v = rng() % n; // multi-edges and self-loops
lowlink g(n);
for (int e = 0; e < m; e++) assert(g.add_edge(edges[e].first, edges[e].second) == e);
g.build();
int base = components(n, edges, -1, -1);
std::vector<int> br, ap;
for (int e = 0; e < m; e++) {
bool b = components(n, edges, -1, e) > base;
assert(g.is_bridge(e) == b);
if (b) br.push_back(e);
}
assert(g.bridges() == br);
for (int v = 0; v < n; v++) {
// removing v also removes v itself from the count
bool a = components(n, edges, v, -1) > base;
assert(g.is_articulation(v) == a);
if (a) ap.push_back(v);
}
assert(g.articulation_points() == ap);
// same 2-edge-connected component <=> connected after removing any single edge
auto groups = g.two_edge_connected_components();
std::vector<int> cnt(groups.size(), 0);
for (int c = 0; c < int(groups.size()); c++) {
for (int v : groups[c]) assert(g.component(v) == c), cnt[c]++;
}
int total = 0;
for (int x : cnt) assert(x > 0), total += x;
assert(total == n);
for (int u = 0; u < n; u++) {
for (int v = u + 1; v < n; v++) {
bool same = true;
// connected in the graph without bridges?
std::vector<std::pair<int, int>> nb;
for (int e = 0; e < m; e++) if (!g.is_bridge(e)) nb.push_back(edges[e]);
std::vector<std::vector<int>> h(n);
for (auto [a, b] : nb) h[a].push_back(b), h[b].push_back(a);
std::vector<bool> seen(n, false);
std::vector<int> st = {u};
seen[u] = true;
while (!st.empty()) {
int x = st.back();
st.pop_back();
for (int y : h[x]) if (!seen[y]) seen[y] = true, st.push_back(y);
}
same = seen[v];
assert((g.component(u) == g.component(v)) == same);
}
}
}
// long path: no recursion, so n = 200000 must not overflow the stack
{
int n = 200000;
lowlink g(n);
for (int i = 0; i + 1 < n; i++) g.add_edge(i, i + 1);
g.build();
assert(int(g.bridges().size()) == n - 1);
assert(int(g.articulation_points().size()) == n - 2);
assert(g.two_edge_connected_components().size() == size_t(n));
}
std::cout << "Hello World" << std::endl;
return 0;
}