首页 > 代码库 > 分别利用并查集,DFS和BFS方法求联通块的数量

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

联通块是指给定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;
}

以上三个方法,都是比较容易理解上手的,能够很好的提高做类似题目的能力;