This documentation is automatically generated by online-judge-tools/verification-helper
#include "data_structure/union_enumerate.cpp"
#include "other/int_alias.cpp"
#include <algorithm>
#include <functional>
#include <utility>
#include <vector>
std::vector<std::vector<usize>> three_edge_connected_component_decomposition(
const std::vector<std::vector<usize>> &g) {
const usize n = g.size();
std::vector<usize> in(n);
std::vector<usize> out(n);
std::vector<usize> low(n, n);
std::vector<usize> deg(n, 0);
std::vector<usize> path(n, n);
std::vector<bool> visited(n, false);
union_enumerate tcc(n);
const auto absorb = [&](const usize v, const usize w) -> void {
tcc.unite(v, w);
deg[v] += deg[w];
};
usize count = 0;
const std::function<void(usize, usize)> dfs = [&](const usize v,
usize p) -> void {
visited[v] = true;
in[v] = count;
count += 1;
for (usize w : g[v]) {
if (w == v)
continue;
if (w == p) {
p = n;
continue;
}
if (visited[w]) {
if (in[w] < in[v]) {
deg[v] += 1;
low[v] = std::min(low[v], in[w]);
} else {
deg[v] -= 1;
usize u = path[v];
while (u != n && in[u] <= in[w] && in[w] < out[u]) {
absorb(v, u);
u = path[u];
}
path[v] = u;
}
continue;
}
dfs(w, v);
if (path[w] == n && deg[w] <= 1) {
deg[v] += deg[w];
low[v] = std::min(low[v], low[w]);
continue;
} else if (deg[w] == 0) {
w = path[w];
}
if (low[w] < low[v]) {
low[v] = low[w];
std::swap(w, path[v]);
}
while (w != n) {
absorb(v, w);
w = path[w];
}
}
out[v] = count;
};
for (usize i = 0; i != n; i += 1) {
if (!visited[i])
dfs(i, n);
}
return tcc.get_all();
}
/**
* @brief 3-Edge-Connected Component Decomposition
* @see https://www.sciencedirect.com/science/article/abs/pii/S0020019013002470
*/
#line 2 "other/int_alias.cpp"
#include <cstddef>
#include <cstdint>
using i32 = std::int32_t;
using i64 = std::int64_t;
using u32 = std::uint32_t;
using u64 = std::uint64_t;
using isize = std::ptrdiff_t;
using usize = std::size_t;
#line 2 "data_structure/union_enumerate.cpp"
#include <cassert>
#line 5 "data_structure/union_enumerate.cpp"
#include <numeric>
#include <utility>
#include <vector>
class union_enumerate {
std::vector<usize> next;
public:
union_enumerate() = default;
union_enumerate(const usize size) : next(size) {
std::iota(next.begin(), next.end(), static_cast<usize>(0));
}
usize size() const { return next.size(); }
std::vector<usize> enumerate(const usize x) const {
assert(x < size());
std::vector<usize> ret;
usize y = x;
do {
ret.push_back(y);
y = next[y];
} while (y != x);
return ret;
}
std::vector<std::vector<usize>> get_all() const {
const usize n = size();
std::vector<std::vector<usize>> res;
std::vector<bool> visited(n, false);
for (usize i = 0; i != n; i += 1) {
if (!visited[i]) {
const std::vector<usize> list = enumerate(i);
for (const usize j : list)
visited[j] = true;
res.push_back(list);
}
}
return res;
}
void unite(const usize x, const usize y) {
assert(x < size());
assert(y < size());
std::swap(next[x], next[y]);
}
};
/**
* @brief Union Enumerate
* @see http://noshi91.hatenablog.com/entry/2019/07/19/180606
*/
#line 3 "algorithm/three_edge_connected_component_decomposition.cpp"
#include <algorithm>
#include <functional>
#line 8 "algorithm/three_edge_connected_component_decomposition.cpp"
std::vector<std::vector<usize>> three_edge_connected_component_decomposition(
const std::vector<std::vector<usize>> &g) {
const usize n = g.size();
std::vector<usize> in(n);
std::vector<usize> out(n);
std::vector<usize> low(n, n);
std::vector<usize> deg(n, 0);
std::vector<usize> path(n, n);
std::vector<bool> visited(n, false);
union_enumerate tcc(n);
const auto absorb = [&](const usize v, const usize w) -> void {
tcc.unite(v, w);
deg[v] += deg[w];
};
usize count = 0;
const std::function<void(usize, usize)> dfs = [&](const usize v,
usize p) -> void {
visited[v] = true;
in[v] = count;
count += 1;
for (usize w : g[v]) {
if (w == v)
continue;
if (w == p) {
p = n;
continue;
}
if (visited[w]) {
if (in[w] < in[v]) {
deg[v] += 1;
low[v] = std::min(low[v], in[w]);
} else {
deg[v] -= 1;
usize u = path[v];
while (u != n && in[u] <= in[w] && in[w] < out[u]) {
absorb(v, u);
u = path[u];
}
path[v] = u;
}
continue;
}
dfs(w, v);
if (path[w] == n && deg[w] <= 1) {
deg[v] += deg[w];
low[v] = std::min(low[v], low[w]);
continue;
} else if (deg[w] == 0) {
w = path[w];
}
if (low[w] < low[v]) {
low[v] = low[w];
std::swap(w, path[v]);
}
while (w != n) {
absorb(v, w);
w = path[w];
}
}
out[v] = count;
};
for (usize i = 0; i != n; i += 1) {
if (!visited[i])
dfs(i, n);
}
return tcc.get_all();
}
/**
* @brief 3-Edge-Connected Component Decomposition
* @see https://www.sciencedirect.com/science/article/abs/pii/S0020019013002470
*/