二点連結成分分解・関節点の列挙
計算量
$O(E + V)$
使い方
g- 無向グラフ．任意の辺 (u,v) に対して逆辺 (v,u) を持つグラフとして表現する．
art(戻り値)- 関節点のリストが入る．ある関節点 u が k 個の二重連結成分をつないでいる場合，(k-1) 個の u が入る．嫌なら sort, unique, erase する． UnionFind 木を使って，両側とも art に含まれない辺の両側を union していくと，二重連結成分分解ができる．
実装
std::vector<int> articulationPoint(const Graph& g) {
int n = g.size(), idx;
std::vector<int> low(n), ord(n), art;
std::function<void(int)> dfs = [&](int v) {
low[v] = ord[v] = ++idx;
for (auto& e : g[v]) {
int w = e.dst;
if (ord[w] == 0) {
dfs(w);
low[v] = std::min(low[v], low[w]);
if ((ord[v] == 1 && ord[w] != 2) || (ord[v] != 1 && low[w] >= ord[v]))
art.push_back(v);
} else
low[v] = std::min(low[v], ord[w]);
}
};
for (int u = 0; u < n; u++)
if (ord[u] == 0) {
idx = 0;
dfs(u);
}
// sort(art.begin(), art.end());
// art.erase(unique(art.begin(), art.end()), art.end());
return art;
}