分别利用并查集，DFS和BFS方法求联通块的数量

浏览数：30 / 时间：2015年06月11日

联通块是指给定n个点，输入a,b(1<=a,b<=n)，然后将a,b连接，凡是连接在一起的所有数就是一个联通块；

题意：第一行输入n,m，分别表示有n个数,有输入m对连接点，以下将要输入m行（输入数据到文件截止）；

输出：第一行要求输出联通块的个数，并在第二行分别输出每个联通块中点的数量，每个数之间以一个空格隔开。

样例 1
5 3
1 4
2 5
3 5
输出：2
2 3
样列2

9 8
1 2
2 3
3 4
3 7
4 5
4 6
7 8
7 9
输出：

1
9

如果不明白的话可以画图试试，最多花半个小时，要是早这样不知道能省下多少个半小时呢；

此题可以利用并查集求解：
首先可以将N个点看成独立的联通块，然后每个每个独立的联通块都有一个节点，然后每次连接两个点，就将它们的节点加在一起；
代码如下：
#include<iostream>
#include<cstring>
using namespace std;
const int maxn=1010;
int p[maxn];//作为每个独立的点
int sum[maxn];//每个节点下面连接的点
int find(int x)
{
if(x==p[x])return x;
return p[x]=find(p[x]);//压缩路径
}
int main()
{
int n,m;
while(cin>>n>>m)
{
if(n==0)//如果没有数据那就直接按照格式输出零，一般不会有这种输入
{
cout<<0<<endl<<0<<endl;
continue;
}
for(int i=1;i<=n;i++)//初始化，令每一个点成为独立的联通块
{
p[i]=i;
sum[i]=1;//每个联通块中节点的个数为 1
}

int a,b;
for(int i=1;i<=m;i++)
{
cin>>a>>b;
int fa=find(a);//查找a的头节点
int fb=find(b);//查找b的头节点
if(fa!=fb)//如果头节点不同
{
p[fa]=fb;//将两个点合并
sum[fb]+=sum[fa];//并且使新头节点中的个数加上新连接的联通块所含节点的个数
}
}
int count=0;
for(int i=1;i<=n;i++)
{
if(p[i]==i)//计算联通块的数量
{
count++;
}
}
cout<<count<<endl;
int flag=0;
for(int i=1;i<=n;i++)
{
if(p[i]==i)
{
if(flag==1)cout<<" ";
flag=1;
cout<<sum[i];
}
}
cout<<endl;
}
return 0;
}

这个题目利用DFS求解也可以。

要建立一个二维数据，将要连接点的点连在一起，并且用一个一位数据记录每个点是否被搜索过；

代码如下：

#include<iostream>
#include<cstring>
using namespace std;
const int maxn=1000;
int map[maxn][maxn];
int vis[maxn];
int tot;
int n,m;
void dfs(int s)
{
tot++;
vis[s]=1;
for(int i=1;i<=n;i++)
if(!vis[i]&&map[s][i])//当从1到n都搜索一遍后变会自动停止
{
dfs(i);
}
}
int main()
{
int now=0;
int v,u;
while(cin>>n>>m)
{
tot=0;
now=0;
int sum[maxn];
memset(map,0,sizeof(map));
memset(vis,0,sizeof(vis));
for(int i=1;i<=m;i++)
{
scanf("%d%d",&u,&v);
map[u][v]=map[v][u]=1;
}
for(int i=1;i<=n;i++)
{
if(vis[i]==0)
{
tot=0;
dfs(i);
sum[++now]=tot;
}
}
cout<<now<<endl;
for(int i=1;i<=now;i++)
{
if(i>1)cout<<" ";
cout<<sum[i];
}
cout<<endl;
}
return 0;
}

利用BFS做也是比较方便的；

利用队栈保存每次搜索到的数据，并且在处理完成它的子节点后删除；同时利用一个数组记录是否拜访过它；

#include <cstdio>
#include <cstring>
#include<iostream>
#include <queue>
using namespace std;
#define N 100
int n,m;
int map[N][N];
int mk[N];
int sum[N];
int total;
void bfs(int s)
{
queue <int> Q;
Q.push(s);
mk[s]=1;
while(!Q.empty())
{
int u=Q.front();Q.pop();
total++;
for(int i=1;i<=n;i++)
{
if(map[u][i]&&!mk[i])
{
mk[i]=1;
Q.push(i);
}
}
}
}
int main()
{
int u,v;
int now=0;
while(scanf("%d%d",&n,&m)==2)
{
now=0;
memset(map,0,sizeof(map));
memset(mk,0,sizeof(mk));
for(int i=1;i<=m;i++)
{
scanf("%d%d",&u,&v);
map[u][v]=map[v][u]=1;
}
for(int i=1;i<=n;i++)
{if(mk[i]==0)
{
total=0;
bfs(i);
sum[++now]=total;
}
}
cout<<now<<endl;
for(int i=1;i<=now;i++)
{
if(i>1)cout<<" ";
cout<<sum[i];
}
cout<<endl;
}
return 0;
}