标题问题链接：?id=1144

标题问题大意：给予一个无向图，求割点数量。

这道标题问题的输入和我们一般见到的不太一样。
它首先输入 \(N\)（\(\lt 100\)）暗示点的数量（\(N=0\)暗示文件输入结束）。
然后接下来每行输入一组数字。

如果这一组数字只包罗一个 \(0\) ，说明本组测试数据输入结束；

否则，假设这些数可以拆分成 \(a_1,a_2,a_3, \cdots ,a_m\)，则说明 \(a_1\) 这个点到 \(a_2,a_3, \cdots , a_m\) 之间都存在着一条边。

所以这道标题问题想要表达的意思还是一样的 \(\Rightarrow\) 求割点的数量，只不过输入方法和我们平时见到的不太一样。

不雅察看DFS搜索树，我们可以发明有两类节点可以成为割点：

对根节点 \(u\) ，若其有两棵或两棵以上的子树，则该根结点 \(u\) 为割点；

对非叶子节点 \(u\) （非根节点），若其子树的节点均没有指向 \(u\) 的祖先节点的回边，说明删除 \(u\) 之后，根结点与 \(u\) 的子树的节点不再连通，有 \(low[v] \ge dfn[u]\) ；则节点 \(u\) 为割点。

实现代码如下：

#include <iostream> #include <string> #include <sstream> #include <vector> #include <cstdio> using namespace std; const int maxn = 10010; int n, m, dfn[maxn], low[maxn], f[maxn], cnt, ans; bool vis[maxn]; vector<int> g[maxn]; void init() { ans = cnt = 0; for (int i = 1; i <= n; i ++) { low[i] = dfn[i] = f[i] = vis[i] = 0; g[i].clear(); } } void tarjan(int u) { low[u] = dfn[u] = ++cnt; int son_num = 0; // 记录子树数量 int sz = g[u].size(); for (int i = 0; i < sz; i ++) { int v = g[u][i]; if (!dfn[v]) { // v未被访谒，，(u,v)为树边 son_num ++; f[v] = u; tarjan(v); low[u] = min(low[u], low[v]); if (dfn[u] == 1 && son_num > 1 && !vis[u]) { // 根节点，子树数量大于1即为割点 vis[u] = true; ans ++; } else if (dfn[u] != 1 && low[v] >= dfn[u] && !vis[u]) { // 其余节点子树可追溯到最早的祖先节点要么为v要么为u vis[u] = true; ans ++; } } else if (f[v] != u) { // 节点v已被访谒，则(u,v)为回边 low[u] = min(low[u], dfn[v]); } } } int main() { while (~scanf("%d", &n) && n) { init(); getchar(); string s; int a, b; while (getline(cin, s)) { stringstream ss(s); ss >> a; if (!a) break; while ((ss >> b) && b) { g[a].push_back(b); g[b].push_back(a); } } tarjan(1); cout << ans << endl; } return 0; }

参考链接：

https://www.cnblogs.com/zjl192628928/p/10467126.html

POJ1144 Network 题解 点双连通分量（求割点数量）