强连通-割点（曾老代码）

57 阅读 0 评论 38 点赞

我是靠谱客的博主着急热狗，最近开发中收集的这篇文章主要介绍强连通-割点（曾老代码），觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

//割点模板，邻接矩阵实现O(N^2)，最好改为邻接表O(N+M)
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<string>
#include<cmath>
#include<algorithm>
using namespace std;

struct Edge
{
int u,v,next;
}e[101];
int first[101],cnt; //cnt边的数量（编号）

int n,m,root;
int num[101],low[101],flag[101],index=0; //index用来进行时间戳的递增；flag:标记割点
int x,y;

void addedge(int u,int v) //建立邻接表
{
e[cnt].u=u; e[cnt].v=v;
e[cnt].next=first[u];first[u]=cnt++;
}

void dfs(int cur,int father) //cur:当前顶点的编号；father:父顶点的编号
{
int child=0; //child:记录生成树中当前顶点cur的儿子个数
index++; //时间戳加1
num[cur]=index; //当前顶点cur的时间戳
low[cur]=index; //当前顶点cur能够访问到最早顶点的时间戳(刚开始当然是自己)

for(int i=first[cur];i!=-1;i=e[i].next) //枚举所有从当前顶点cur出发的边i
{
if(num[e[i].v]==0) //如果第i条边终点v的时间戳为0，说明顶点v还没有被访问过
{ //点v为cur的儿子
child++; //儿子数量加1
dfs(e[i].v,cur); //从cur的儿子v继续往下DFS
low[cur]=min(low[cur],low[e[i].v]); //更新当前顶点cur能访问到最早顶点的时间戳
if(cur!=root && low[e[i].v]>=num[cur]) flag[cur]=1; //如果当前顶点cur不是根结点并且满足low[v]>=num[cur])，则当前顶点cur为割点
if(cur==root && child==2) flag[cur]=1; //如果当前顶点cur是根结点，生成树中根结点必须有两个儿子，根结点才是割点
}
else //如果顶点v曾经被访问过，并且v不是当前顶点cur的父亲，则说明此时的v为cur的祖先
if(e[i].v!=father) low[cur]=min(low[cur],num[e[i].v]); //因此需要更新当前结点cur能访问到最早顶点的时间戳
}
return;
}

int main()
{
freopen("gedian.in","r",stdin);
freopen("gedian.out","w",stdout);
memset(first,-1,sizeof(first));
cnt=0; //边的数量（编号）

scanf("%d %d",&n,&m);
for(int i=1;i<=m;i++) //读入无向图的m条边
{
scanf("%d %d",&x,&y);
addedge(x,y); //建立邻接表
addedge(y,x); //反向建立邻接表
}

root=1; //设整个图的根为1
dfs(1,root); //从1号顶点开始DFS，root是1的父亲

for(int i=1;i<=n;i++) //枚举所有点
if(flag[i]==1) printf("%d ",i); //输出割点
printf("n");

return 0;
}