题解：P3388 【模板】割点（割顶）

changxiang2012 · 2025-05-18 15:15:26 · 题解

割点（割顶）问题的 Tarjan 算法解析

割点（Cut Vertex），也称为割顶，是无向连通图中的一个重要概念。如果删除某个顶点后，图的连通分量数目增加，则称该顶点为割点。在通信网络中，割点可能代表关键节点，其故障会导致网络分裂。

题目分析

本题要求找出给定无向图中的所有割点，并按编号从小到大输出。输入为图的顶点数和边数，以及每条边的连接信息；输出为割点的数量和具体编号。

关键约束条件：

顶点数 n 最大为 20,000。
边数 m 最大为 100,000。
图可能不连通，需要处理所有连通分量。

Tarjan算法原理

Tarjan 算法是一种高效的图论算法，通过深度优先搜索（DFS）来寻找图的割点、桥和强连通分量。其核心思想是利用时间戳（dfn）和回溯值（low）来判断顶点间的连通关系。

时间戳 dfn[u]：顶点 u 在 DFS 遍历中第一次被访问的顺序号。
回溯值 low[u]：顶点 u 及其子树中的节点通过非父子边（回边）所能追溯到的最早时间戳。

AC代码

下面是解决该问题的 Tarjan 算法实现：

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <string>
#include <cstring>
#include <cctype>
#include <sstream>
#include <vector>
#include <queue>
#include <stack>
#include <deque>
#include <set>
#include <map>
#include <ctime>
#include <cstdlib>
#include <iomanip>
#include <bitset>
#define N 100010 
using namespace std;
struct add{int v,next;}e[2 * N];
int head[N],dfn[N],low[N],n,m,cnt = 1,num = 0,root;
bool cut[N];
inline void ins(int x,int y){
    e[++cnt].v = y;
    e[cnt].next = head[x];
    head[x] = cnt;
}
inline void tarjan(int x){
    dfn[x] = low[x] = ++num;
    int flag = 0;
    for(int i = head[x];i;i = e[i].next){
        int y = e[i].v;
        if(!dfn[y]){
            tarjan(y);
            low[x] = min(low[x],low[y]);
            if(low[y] >= dfn[x]){
                ++flag;
                if(x != root || flag > 1){
                    cut [x] = 1;
                }
            }
        }else low[x] = min(low[x],dfn[y]);
    } 
}
int main(){
    ios::sync_with_stdio(false);//关闭cin流同步,不能使用scanf printf;
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>m;
    for(int i = 1;i <= m;i++){
        int x,y;
        cin>>x>>y;
        ins(x,y);
        ins(y,x);
    }
    for(int i = 1;i <= n;i++){
        if(!dfn[i]){
            root = i,tarjan(i);
        }
    }
    int tot = 0;
    for(int i = 1;i <= n;i++){
        if(cut[i]){
            ++tot;
        }
    }
    cout<<tot<<endl;
    for(int i = 1;i <= n;i++){
        if(cut[i]){
            cout<<i<<" ";
        }
    }
    return 0;
}
/*

*/

算法关键点解析

邻接表存储图结构：使用数组模拟链表，高效存储稀疏图。每个顶点的所有邻接边构成一个链表。
Tarjan 算法核心逻辑：
- 对每个顶点进行 DFS 遍历，记录时间戳 dfn 和回溯值 low。
- 对于根节点，若其子树数量大于 1，则为割点
- 对于非根节点，若存在子树 v 满足 low[v] \ge dfn[u]，则 u 为割点。
处理非连通图：遍历所有顶点，对每个未访问的顶点作为根节点进行 Tarjan 算法。
时间复杂度分析：算法对每个顶点和每条边仅遍历一次，时间复杂度为 O(n + m)，适用于大规模图。

示例测试

以题目中的样例输入为例：

运行算法后，顶点 5 被标记为割点，因为删除顶点5后，图将分为两个连通分量： {1,2,3,4} 和 {6}。输出结果为：

1
5

感谢@whoseJam的讲解