#include "definition.cpp"
template <typename edge_t>
std::pair<std::set<int>, std::vector<std::vector<edge_t>>>
articulation_points(const graph_t<edge_t> &g) {
const int n = g.size();
std::set<int> art;
std::vector<std::vector<edge_t>> connect;
std::vector<edge_t> st;
std::vector<int> order(n, -1), low(n, -1);
for (int i = 0; i < n; i++) {
if (order[i] != -1) continue;
int cnt = 0;
std::function<void(int, int)> dfs = [&](int from, int parent) {
low[from] = order[from] = cnt++;
for (edge_t e : g[from]) {
const int to = e.to;
if (to != parent && order[to] < order[from]) st.push_back(e);
if (order[to] == -1) {
dfs(to, from);
low[from] = std::min(low[from], low[to]);
if ((order[from] == 0 && order[to] != 1) ||
(order[from] != 0 && low[to] >= order[from]))
art.insert(from);
if (low[to] >= order[from]) {
connect.push_back(std::vector<edge_t>());
for (;;) {
edge_t edge = st.back();
st.pop_back();
connect.back().push_back(edge);
if (edge.from == from && edge.to == to) break;
}
}
}
else {
low[from] = std::min(low[from], order[to]);
}
}
};
dfs(i, i);
}
return make_pair(move(art), move(connect));
}
Includes
Back