洛谷U640022 找割点 题解 点双连通分量

题目链接：https://www.luogu.com.cn/problem/U640022

• 根节点要分割出至少 \(2\) 个连通块（因为根节点没有父节点那部分的连通块）。
• 其它节点只需要分割出至少 \(1\) 个连通块即可。

对于一个 当前节点 \(u\)，dfs 它的某个子节点 \(v\) 之后，满足 low[v] >= dfn[u]，就说明能分隔出一个连通块了（因为 \(v\) 回不到 \(u\) 头上去了）。

示例程序：

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 5;vector<int> g[maxn];
int n, m, dfn[maxn], low[maxn], ts;
set<int> st;void tarjan(int u, int p) {dfn[u] = low[u] = ++ts;int son_cnt = 0;for (auto v : g[u]) {if (v == p) continue;if (!dfn[v]) {tarjan(v, u);low[u] = min(low[u], low[v]);if (low[v] >= dfn[u])son_cnt++;}else low[u] = min(low[u], dfn[v]);}if (son_cnt >= 2 || u != 1 && son_cnt == 1)st.insert(u);
}int main() {scanf("%d%d", &n, &m);for (int i = 0, u, v; i < m; i++) {scanf("%d%d", &u, &v);g[u].push_back(v);g[v].push_back(u);}tarjan(1, -1);if (st.size() == 0)puts("no");else {for (auto u : st)printf("%d\n", u);}return 0;
}