这个算法的关键在于:当深度优先遍历访问到顶点u时,假设图中还有顶点v是没有访问过的点,如何判断顶点v在不经过u
的情况下还能回到之前访问任意一个结点?如果从生成树的角度来说,顶点u就是顶点v的的父亲,而之前已经被访问过的顶点
就是祖先。换句话说,如何检测顶点v在不经过父顶点u的情况下还能否回到祖先。我的方法是对顶点v再进行一次深度优先遍历,但此次遍历不允许经过顶点u,看看能否回到祖先,如果不能回到祖先说明顶点u是割点。
low[i]来记录每个顶点在不经过父顶点时,能够回到的最小时间戳。
代码是用邻接矩阵来存储图的,复杂度O(N^2),边的处理就需要O(N^2)。这样写是为了突出割点部分。实际应用改为邻接表来存储,这样复杂度为O(N+M)
#include <bits/stdc++.h>
using namespace std;
const int maxn=505;
int n,m,e[maxn][maxn];
int root,num[maxn],low[maxn],flag[maxn],index;
void dfs(int cur,int father)//割点算法核心 当前结点,父亲结点
{
int child=0,i;//child用来记录在生成树中当前顶点cur儿子的个数
index++;//时间戳加加
num[cur]=index;//当前顶点cur时间戳
low[cur]=index;//初始化最早能访问到的时间戳,当然是自己了
for(int i=1;i<=n;i++)
{
if(e[cur][i]==1)//遍历所有与当前点联通的点
{
if(num[i]==0)//当前点未访问
{
child++;//从生成树的角度来说就是i是cur的儿子
dfs(i,cur);//继续往下深度优先遍历
low[cur]=min(low[cur],low[i]);//更新时间戳(不经过父亲结点能回到的最小时间戳)
if(cur!=root&&low[i]>=num[cur])
flag[cur]=1; //当前结点不是根结点,满足low[i]>=num[cur],cur为割点
if(cur==root&&child>=2)
flag[cur]=1;//当前结点是根节点,则必须有两个儿子才是割点
}
else if(i!=father)//已经访问但是 这个点不是cur的父亲,
//则说明此时的i为cur的祖先,因此需要更新当前结点cur能访问到的最早结点
{
low[cur]=min(low[cur],num[i]);
}
}
}
}
int main()
{
scanf("%d %d",&n,&m);
memset(e,0,sizeof(e));
memset(flag,0,sizeof(flag));
for(int i=0;i<m;i++)
{
int a,b;
scanf("%d %d",&a,&b);
e[a][b]=1;
e[b][a]=1;//建立边
}
root=1;//根节点是1
dfs(1,root);
for(int i=1;i<=n;i++)
{
if(flag[i]==1)
printf("%d ",i);
}
return 0;
}
in 6 7 1 4 1 3 4 2 3 2 2 5 2 6 5 6 out 2