割边:如果删除某条边,图不再连通。
如何求割边呢?只需要将求割点的算法修改一个符号就可以。只需将lowv>=numu改为lowv>numu,取消一个等号即可。
为什么呢?lowv>=numu代表的是点v是不可能在不经过父节点u而回到祖先(包括父亲)的,所以顶点u是割点。
如果lowv和numu相等表示还可以回到父亲,而lowv>numu则表示连父亲都回不到了。倘若顶点v不能回到祖先,也没有
另外一条路能回到父亲,那么u-v这条边就是割边
#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 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)//当前点未访问
{
dfs(i,cur);//继续往下深度优先遍历
low[cur]=min(low[cur],low[i]);//更新时间戳(不经过父亲结点能回到的最小时间戳)
if(low[i]>num[cur])
printf("%d-%d\n",cur,i);
}
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);
return 0;
}