问题描述：
给出一张连通的无向图 输出图中的所有连通分量
代码：
#include<iostream>#include<cstdio>#include<cstring>#define maxn 1050using namespace std;struct node{int from,to,next,vis;int equall(node b){if((from==b.from)&&to==b.to||(from==b.to&&to==b.from))return 1;return 0;}}edge[maxn*100],Edge;//int head[maxn];//邻接表 int e_num;//int dfn[maxn],low[maxn];int num;node stk[maxn*100];int top;int ss;void init(){memset(head,-1,sizeof(head));memset(dfn,0,sizeof(dfn));num=1;e_num=0;top=-1;ss=0;}void addedge(int a,int b){edge[e_num]={a,b,head[a],0};head[a]=e_num++;edge[e_num]={b,a,head[b],0};head[b]=e_num++;}void Tarjan(int u){dfn[u]=low[u]=num++;for(int i=head[u];i!=-1;i=edge[i].next){if(!edge[i].vis){edge[i].vis=edge[i^1].vis=1;//防止回边(同一条边)重复入栈stk[++top]=edge[i];//压栈int v=edge[i].to;if(!dfn[v]){Tarjan(v);low[u]=min(low[u],low[v]);if(dfn[u]<=low[v])//发现u是割点 —–构成一个连通分量{printf("连通分量%d:\n",++ss);while(1){if(top<0)break;printf("%d-%d ",stk[top].from,stk[top].to);top–;if(edge[i].equall(stk[top+1]))break;}cout<<endl;}}else low[u]=min(low[u],dfn[v]);}}}int main(){int n,m;int a,b;while(1){printf("请输入点数和边数:\n");scanf("%d%d",&n,&m);init();for(int i=1;i<=m;i++){printf("请输入第%d条边:\n",i);scanf("%d%d",&a,&b);addedge(a,b);}Tarjan(1);}return 0;}
版权声明：本文为博主原创文章，，未经博主允许不得转载。
生活的最大悲剧不是失败，而是一个人已经习惯于失败。
