求无向图的连通分量

定义

无向图G的最大连通子图称为G的连通分量( Connected Component)。任何连通图的连通分量只有一个，即是其自身，非连通的无向图有多个连通分量。

方法一【邻接矩阵DFS】

邻接矩阵，DFS解

#include<iostream> #include<cstdio> using namespace std; bool f[105][105],a[105]; //f邻接矩阵，a给走过的顶点做标记 int m,n,ans; void ooo(int s) { a[s]=1; //标记 for(int i=1;i<=n;i++) { if(!a[i]&&f[s][i]) //当两点连通并且此点没有被访问过 { m++; //累计总数 a[i]=1; //标记 ooo(i); //DFS } } } int main() { int x,y; scanf("%d%d%d",&n,&x,&y); while(x&&y) //末尾是0 0时结束输入 { f[x][y]=1; f[y][x]=1; //无向图要双向处理 scanf("%d%d",&x,&y); } for(int i=1;i<=n;i++) { m=0; //m记录当前顶点连通的所有顶点数 if(!a[i]) //当此点没有被访问过 { ooo(i); ans=max(ans,m); //判断最大数 } } printf("%d",ans+1); //+1是因为连通的顶点数还要加上它本身的一个点 return 0; }

方法二【邻接表DFS】

方法和上面的差不多，就是换了一个更加高大上 的 存储方式

#include<iostream> #include<cstdio> using namespace std; struct ooo { int y,next; }f[1005]; int n,h[105],k,ans,m; bool a[105]; void lil(int s) { a[s]=1; //标记 for(int i=h[s];i;i=f[i].next) { if(!a[f[i].y]) //没有访问过的情况下 { m++; lil(f[i].y); } } } int main() { int aa,bb; scanf("%d%d%d",&n,&aa,&bb); while(aa&&bb) { f[++k]=(ooo){bb,h[aa]}; h[aa]=k; f[++k]=(ooo){aa,h[bb]}; h[bb]=k; //简单版读入邻接表 scanf("%d%d",&aa,&bb); } for(int i=1;i<=n;i++) { m=0; if(!a[i]) { lil(i); ans=max(ans,m); } } printf("%d",ans+1); return 0; }

方法三【邻接矩阵BFS】

跟上面差不多。就是换成了BFS。。。

#include<iostream> #include<cstdio> using namespace std; bool a[105],f[105][105]; int n,ans,m; void ooo(int s) { int h=0,t=1,x[105]; a[s]=1; x[1]=s; do { h++; for(int i=1;i<=n;i++) if(f[x[h]][i]&&!a[i]) { m++; a[i]=1; x[++t]=i; } }while(h<t); } int main() { int x,y; scanf("%d%d%d",&n,&x,&y); while(x&&y) { f[x][y]=1; f[y][x]=1; scanf("%d%d",&x,&y); } for(int i=1;i<=n;i++) if(!a[i]) { m=0; ooo(i); ans=max(ans,m); } printf("%d",ans+1); return 0; }