解题思路
割点(割顶):在一个无向图中,如果删除某个顶点以及与之相连的所有边后,图的连通分量数量增加,则该顶点称为割点。
Tarjan算法求割点的核心思想:
-
使用深度优先搜索遍历图
-
维护两个数组:
-
dfn[i]
:顶点i的深度优先搜索遍历序号(时间戳) -
low[i]
:顶点i能够回溯到的最早的祖先节点的dfn值
-
-
割点的判断条件:
-
对于根节点:如果有2个或以上的子树,则它是割点
-
对于非根节点:如果存在子节点y满足
low[y] >= dfn[x]
,则x是割点#include<bits/stdc++.h> #define ll long long using namespace std; const int N = 2e5 + 10,inf = 0x3f3f3f3f; vector<int> g[N]; // 邻接表存储图 int dfn[N],low[N],f[N],id; // dfn:时间戳,low:能回溯到的最小dfn,f:父节点,id:时间戳计数器 int vis[N]; // 标记节点是否为割点 int ans; // 割点数量 int n,m; // 顶点数,边数void tarjan(int x,int fa) // Tarjan算法,x:当前节点,fa:父节点 {dfn[x] = low[x] = ++id; // 初始化当前节点的dfn和low值f[x] = fa; // 记录父节点int cnt = 0; // 记录当前节点的子节点数量(用于判断根节点是否为割点)for(int i = 0; i < g[x].size(); i++){int y = g[x][i]; // 邻接节点yif(dfn[y] == 0){ // 如果y未被访问过(树边)cnt++; // 子节点计数+1tarjan(y,x); // 递归遍历子节点 low[x] = min(low[x],low[y]); // 更新当前节点的low值// 判断割点条件:if(f[x] == 0){ // 如果x是根节点if(cnt >= 2) vis[x] = 1; // 根节点有>=2个子树则是割点 }else if(low[y] >= dfn[x]) vis[x] = 1; // 非根节点:存在子节点y满足low[y]>=dfn[x] }else if(y != f[x]) low[x] = min(low[x],dfn[y]); // 回边,更新low值 } }int main() {cin >> n >> m;// 读入图数据,构建无向图for(int i = 1; i <= m; i++){int x,y; cin >> x >> y;g[x].push_back(y);g[y].push_back(x);}// 遍历所有连通分量(因为图可能不连通)for(int i = 1; i <= n; i++){if(dfn[i] == 0) // 如果节点i未被访问过tarjan(i,0); // 从i开始Tarjan算法,父节点设为0(表示根节点) }// 统计割点数量for(int i = 1; i <= n; i++)if(vis[i]) ans++;// 输出结果cout << ans << endl;for(int i = 1; i <= n; i++)if(vis[i])cout << i << " ";return 0; }
-