sotanishy's code snippets for competitive programming
#include "graph/lowlink.hpp"
Lowlink はグラフの橋や関節点などを求める際に有効な概念である.グラフの DFS tree において,頂点 $v$ の訪問時刻を ord[v]
としたとき,$v$ から後退辺 (DFS tree に含まれない辺) を高々1回用いて到達することができる頂点の ord
の最小値 low[v]
を lowlink という.
辺 $(u, v)$ が橋であることの必要十分条件は ord[u] < low[v]
が成り立つことである.
頂点 $v$ が関節点であることの必要十分条件は
ord[v] <= low[c]
が成り立つのどちらかが成り立つことである.
空間計算量: $O(V + E)$
Lowlink(vector<vector<int>> G)
bool is_bridge(int u, int v)
#pragma once
#include <algorithm>
#include <utility>
#include <vector>
class Lowlink {
public:
std::vector<int> ord, low;
std::vector<std::pair<int, int>> bridge;
std::vector<int> articulation;
Lowlink() = default;
explicit Lowlink(const std::vector<std::vector<int>>& G)
: ord(G.size(), -1), low(G.size()), G(G) {
for (int i = 0; i < (int)G.size(); ++i) {
if (ord[i] == -1) dfs(i, -1);
}
}
bool is_bridge(int u, int v) const {
if (ord[u] > ord[v]) std::swap(u, v);
return ord[u] < low[v];
}
private:
std::vector<std::vector<int>> G;
int k = 0;
void dfs(int v, int p) {
low[v] = ord[v] = k++;
bool is_articulation = false, checked = false;
int cnt = 0;
for (int c : G[v]) {
if (c == p && !checked) {
checked = true;
continue;
}
if (ord[c] == -1) {
++cnt;
dfs(c, v);
low[v] = std::min(low[v], low[c]);
if (p != -1 && ord[v] <= low[c]) is_articulation = true;
if (ord[v] < low[c]) bridge.push_back(std::minmax(v, c));
} else {
low[v] = std::min(low[v], ord[c]);
}
}
if (p == -1 && cnt > 1) is_articulation = true;
if (is_articulation) articulation.push_back(v);
}
};
#line 2 "graph/lowlink.hpp"
#include <algorithm>
#include <utility>
#include <vector>
class Lowlink {
public:
std::vector<int> ord, low;
std::vector<std::pair<int, int>> bridge;
std::vector<int> articulation;
Lowlink() = default;
explicit Lowlink(const std::vector<std::vector<int>>& G)
: ord(G.size(), -1), low(G.size()), G(G) {
for (int i = 0; i < (int)G.size(); ++i) {
if (ord[i] == -1) dfs(i, -1);
}
}
bool is_bridge(int u, int v) const {
if (ord[u] > ord[v]) std::swap(u, v);
return ord[u] < low[v];
}
private:
std::vector<std::vector<int>> G;
int k = 0;
void dfs(int v, int p) {
low[v] = ord[v] = k++;
bool is_articulation = false, checked = false;
int cnt = 0;
for (int c : G[v]) {
if (c == p && !checked) {
checked = true;
continue;
}
if (ord[c] == -1) {
++cnt;
dfs(c, v);
low[v] = std::min(low[v], low[c]);
if (p != -1 && ord[v] <= low[c]) is_articulation = true;
if (ord[v] < low[c]) bridge.push_back(std::minmax(v, c));
} else {
low[v] = std::min(low[v], ord[c]);
}
}
if (p == -1 && cnt > 1) is_articulation = true;
if (is_articulation) articulation.push_back(v);
}
};