【模板】割点（割顶）

GitHub跳转原题关系图返回列表

在无向图上跑一遍 Tarjan，若某个儿子 v 满足 low[v] >= dfn[u]，就说明删掉 u 会让这棵子树断开；根节点还要单独判断子树个数。

OJ: luogu

题目 ID: P3388

难度:普及+/提高

标签:图论tarjan割点

日期: 2026-06-20 01:57

目录

  1. 题意
    1. 样例图
  2. 思路
  3. 代码
  4. 复杂度
  5. 总结
  6. 一图流解析

题意

给一张无向图，要求输出所有割点。

割点的意思是：

  • 删除这个点以及和它相连的所有边以后
  • 整张图的连通块数量会变多

题目还特别提醒了一句：

  • 图不一定连通

所以最终代码不能只从 1 号点搜一遍，而要把所有连通块都处理到。

样例图

这张图把样例画出来：

graph G {
  1 -- 2;
  1 -- 3;
  1 -- 4;
  2 -- 5;
  3 -- 5;
  4 -- 5;
  5 -- 6;
}

从图上可以看到，点 5 连着点 6 这条尾巴。 如果删掉点 5，点 6 就彻底和其他点断开，所以 5 是割点。 而删掉 1、2、3、4 中任意一个，剩下部分仍然连通，因此它们不是割点。

思路

先看一个最直接的小数据暴力：

cpp
// brute.cpp：依次删除每个点，重新数连通块，判断它是不是割点。
// 这个做法复杂度较高，只适合小数据理解和对拍。
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 20;
const int MAXM = 50;

struct Edge {
    int u, v;
} edges[MAXM];

int n, m;
vector<int> g[MAXN];
bool vis[MAXN];

void build_graph(int ban) {
    for (int i = 1; i <= n; i++) {
        g[i].clear();
        vis[i] = false;
    }

    for (int i = 1; i <= m; i++) {
        int u = edges[i].u;
        int v = edges[i].v;

        if (u == ban || v == ban) {
            continue;
        }
        g[u].push_back(v);
        g[v].push_back(u);
    }
}

void dfs(int u, int ban) {
    vis[u] = true;
    for (size_t i = 0; i < g[u].size(); i++) {
        int v = g[u][i];
        if (v == ban || vis[v]) {
            continue;
        }
        dfs(v, ban);
    }
}

int count_components(int ban) {
    build_graph(ban);

    int cnt = 0;
    for (int i = 1; i <= n; i++) {
        if (i == ban || vis[i]) {
            continue;
        }
        cnt++;
        dfs(i, ban);
    }
    return cnt;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> m;
    for (int i = 1; i <= m; i++) {
        cin >> edges[i].u >> edges[i].v;
    }

    int base_cc = count_components(0);
    vector<int> answer;

    for (int i = 1; i <= n; i++) {
        int cc = count_components(i);
        if (cc > base_cc) {
            answer.push_back(i);
        }
    }

    cout << answer.size() << '\n';
    for (size_t i = 0; i < answer.size(); i++) {
        cout << answer[i] << ' ';
    }
    cout << '\n';

    return 0;
}

暴力的想法是：

  1. 依次假设删掉一个点 u
  2. 重新统计删点后的连通块个数
  3. 如果连通块数量变多，u 就是割点

这个方法容易理解，但每个点都要重新搜一遍图，复杂度太高。

正式做法就是你书里的 Tarjan 割点模板。

设 u 在 DFS 树里有一个儿子 v。如果：

low[v] >= dfn[u]

说明 v 这棵子树无法绕过 u 回到 u 的祖先。 那么一旦删掉 u，v 子树就会和外界断开，所以 u 是割点。

这里要分两种情况：

  1. u 不是 DFS 根
    只要存在一个儿子 v 满足 low[v] >= dfn[u]，u 就是割点。

  2. u 是 DFS 根
    根没有祖先，判定方式不一样。只有当根在 DFS 树里有至少两个儿子时，删掉它才会把这些子树分开。

所以这题最容易错的地方不是公式，而是：

  • 根节点要单独判断
  • 图不一定连通，要从每个未访问点重新开 DFS

代码

cpp
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 20000 + 5;
const int MAXM = 200000 + 5;

int n, m;
int head[MAXN], to[MAXM], nxt[MAXM], edge_cnt;

int dfn[MAXN], low[MAXN], dfs_clock;
bool is_cut[MAXN];
int root;

void init_graph() {
    edge_cnt = 0;
    dfs_clock = 0;
    for (int i = 1; i <= n; i++) {
        head[i] = -1;
        dfn[i] = 0;
        low[i] = 0;
        is_cut[i] = false;
    }
}

void add_edge(int u, int v) {
    to[edge_cnt] = v;
    nxt[edge_cnt] = head[u];
    head[u] = edge_cnt;
    edge_cnt++;
}

// u: 当前点
// fa: DFS 树里的父节点
void tarjan(int u, int fa) {
    dfn[u] = low[u] = ++dfs_clock;
    int child = 0;

    for (int i = head[u]; i != -1; i = nxt[i]) {
        int v = to[i];

        if (v == fa) {
            continue;
        }

        if (!dfn[v]) {
            child++;
            tarjan(v, u);

            low[u] = min(low[u], low[v]);

            // 非根节点：如果某个儿子回不到 u 的祖先，那么 u 是割点。
            if (u != root && low[v] >= dfn[u]) {
                is_cut[u] = true;
            }
        }
        else if (dfn[v] < dfn[u]) {
            // 返祖边只能用祖先的 dfn 更新 low。
            low[u] = min(low[u], dfn[v]);
        }
    }

    // 根节点需要单独判断：它必须至少有两棵 DFS 子树。
    if (u == root && child > 1) {
        is_cut[u] = true;
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> m;
    init_graph();

    for (int i = 1; i <= m; i++) {
        int u, v;
        cin >> u >> v;
        add_edge(u, v);
        add_edge(v, u);
    }

    for (int i = 1; i <= n; i++) {
        if (!dfn[i]) {
            root = i;
            tarjan(i, 0);
        }
    }

    int cnt = 0;
    for (int i = 1; i <= n; i++) {
        if (is_cut[i]) {
            cnt++;
        }
    }

    cout << cnt << '\n';
    for (int i = 1; i <= n; i++) {
        if (is_cut[i]) {
            cout << i << ' ';
        }
    }
    cout << '\n';

    return 0;
}

复杂度

每个点访问一次，每条无向边最多看两次，所以：

  • 时间复杂度 O(n+m)O(n+m)
  • 空间复杂度 O(n+m)O(n+m)

总结

这题是标准割点模板题，核心记忆点只有两个：

  1. 非根节点看 low[v] >= dfn[u]
  2. 根节点看 DFS 子树数是否至少为 2

理解了这两个判定，后面的点双连通分量题就会自然很多。

一图流解析

这张图把本题的建模、关键转移、实现检查和训练方法压缩到一页，适合读完正文后复盘。

一图流解析