求无向连通图的割点和割边/桥

代码直接整合了求割点和割边：

//求无向连通图的割点和割边/桥#include <cstdio>#include <cstring>#include <iostream>using namespace std;#define MAXN 1000#define MAXM 10000struct node{	int to;	int next;}edge[MAXM];int head[MAXN];int cnt;int n,m;int index;//时间戳int cut[MAXN];//存割点int bridge[MAXN][MAXN];//存割边int dfn[MAXN],low[MAXN];//dfn:时间戳;low:可以到达的 访问时间最早的 祖先(访问时间比自己早的节点看作自己的祖先)void Init(){	cnt=0;	index=0;	memset(head,0,sizeof(head));	memset(edge,0,sizeof(edge));	memset(cut,0,sizeof(cut));	memset(bridge,0,sizeof(int)*MAXN*MAXN);	memset(dfn,0,sizeof(dfn));}void Add(int x,int y){	cnt++;	edge[cnt].to=y;	edge[cnt].next=head[x];	head[x]=cnt;}void cut_bridge(int cur,int father){	int child=0;	index++;	dfn[cur]=index;	low[cur]=index;	for(int i=head[cur];i;i=edge[i].next){		if(dfn[edge[i].to]&&edge[i].to!=father){			if(dfn[edge[i].to]<low[cur]){				low[cur]=dfn[edge[i].to];			}		}		if(!dfn[edge[i].to]){			cut_bridge(edge[i].to,cur);//可以看出，具体搜索的过程还是下一步走未访问的点			child++;			if(low[edge[i].to]<low[cur]){				low[cur]=low[edge[i].to];			}			if((father==0&&child>1)||(father!=0&&low[edge[i].to]>=dfn[cur])){				cut[cur]=1;			}			if(low[edge[i].to]>dfn[cur]){				bridge[cur][edge[i].to]=bridge[edge[i].to][cur]=1;			}		}	}}int main(){	int x,y;	freopen("1.txt","r",stdin);	cin>>n>>m;	Init();	for(int i=1;i<=m;i++){		cin>>x>>y;		Add(x,y);		Add(y,x);	}	cut_bridge(1,0);	return 0;}对于非连通图，对于每个连通分量取一个点调用cut_bridge()函数即可