Tarjan求无向图割点

Tarjan算法的核心思想已经在《Tarjan求无向图割边》中介绍了，不清楚的读者可以先行阅读那部分内容，这里直接从介绍割点开始。

无向图的割点及判定

.

对于无向连通图$G(V,E)$，若删去点$v\in V$及其邻边$\forall u\in {V-v}, (v,u)\in E$后，$G$被分为两个或更多互不连通的子图，则称$v$为割点或割顶。

根据上面$dfn$和$low$，很容易能想出割边的方法——无向边$(u,v)$是割边，当且仅当搜索树上存在$u$的一个子节点$v$，满足：

$$dfn[u]\leq low[v]$$

如果不明白上式，可以参考之前文章中抽象的三种图形。当$dfn[u]=low[v]$时，两条链合起来状似闭环，此时无割边，但两条链$dfn$最小的咬合点显然是割点。

特别的，对于我们搜索的起点，上述判定方法还需限定条件，先来看一个反例：

graph LR
A((1/1))
B((2/1))
C((3/1))
D((4/1))
A === B
B === C
C === D
D --- A

上图中，有唯一满足$dfn[u]\leq low[v]$的$(1,2)$，但去掉$1$后，剩余图为：

graph LR
B((2))
C((3))
D((4))
B --- C
C --- D

并没有被分为两个或以上的互不连通子图，所以这里搜索起点$1$尽管满足上面的判别式，但并不是割点。

是不是所有的搜索起点都不是割点呢？提出这个问题固然在思考，但细想却很好笑——任意点都能作为搜索起点，如果这句话成立，则任意点都不是割点。

对搜索起点的处理

如果搜索起点有两个以上的子树，则意味着在搜索树上，根结点出度为二或以上。根据树的性质，如果我们删去根节点及其邻边，则原树将裂解成子树个数个互不连通的树。若不明白，任意找几棵树观察便知。

要在代码中实现上述判断，可记录从根节点出发的邻点调用的DFS次数即可，伪代码如下：

int children = 0;
for (int v: G[u]) {
    if (!vis[v]) {
        children++;
        dfs(v);
    }
}
if (children >= 2)  u是割点

对重边的处理

对割点问题而言，删去割点将会将所有相邻的重边删去，所以割点问题并不受重边影响。

参考实现

//
// Created by Visors on 2020/10/29.
//
// 题目名：P3388 【模板】割点（割顶）
// 题目来源：luogu
// 题目链接：https://www.luogu.com.cn/problem/P3388
// 算法：Tarjan
// 用途：无向图割点
// 时间复杂度：O(n+m)
//

#include <bits/stdc++.h>

using namespace std;

struct Tarjan {
    struct Edge {
        int to, next;

        Edge() = default;

        Edge(int to, int next) : to(to), next(next) {}
    };

    int vertexNum{}, edgeNum{};
    int cnt{};              // 当前时间戳
    int root{};             // 保存当前搜索树根
    vector<Edge> edges;
    vector<int> heads;
    vector<int> dfn;        // 时间戳
    vector<int> low;        // 最早追溯时间
    set<int> cuts;          // 割点编号集

    void init(int n, int m) {
        cnt = 0;
        vertexNum = n;
        edgeNum = m;
        heads.resize(vertexNum);
        fill(heads.begin(), heads.end(), -1);
        dfn.resize(vertexNum);
        low.resize(vertexNum);
        cuts.clear();
    }

    void addEdge(int u, int v) {
        edges.emplace_back(v, heads[u]);
        heads[u] = edges.size() - 1;
    }

    void dfs(int u) {
        dfn[u] = low[u] = ++cnt;
        int tot = 0;
        for (int i = heads[u]; ~i; i = edges[i].next) {
            int &v = edges[i].to;
            if (!dfn[v]) {
                dfs(v);
                low[u] = min(low[u], low[v]);
                if (low[v] >= dfn[u]) {
                    tot++;
                    if (u != root || tot > 1) cuts.insert(u);   // 对树根特判
                }
            } else low[u] = min(low[u], dfn[v]);
        }
    }

    void run() {
        for (int i = 0; i < vertexNum; i++)
            if (!dfn[i]) {
                root = i;
                dfs(i);
            }
    }
} tarjan;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr), cout.tie(nullptr);
    int n, m;
    cin >> n >> m;
    tarjan.init(n, m);
    for (int i = 1, u, v; i <= m; i++) {
        cin >> u >> v;
        if (u == v) continue;
        u--, v--;
        tarjan.addEdge(u, v);
        tarjan.addEdge(v, u);
    }
    tarjan.run();
    cout << tarjan.cuts.size() << endl;
    bool first = true;
    for (int it:tarjan.cuts)
        if (first) {
            cout << it + 1;
            first = false;
        } else cout << ' ' << it + 1;
    cout << endl;
    return 0;
}