联通块是指给定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=;
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==)//如果没有数据那就直接按照格式输出零 ，一般不会有这种输入
{
cout<<<<endl<<<<endl;
continue;
}
for(int i=;i<=n;i++)//初始化，令每一个点成为独立的联通块
{
p[i]=i;
sum[i]=;//每个联通块中节点的个数为 1
} int a,b;
for(int i=;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=;
for(int i=;i<=n;i++)
{
if(p[i]==i)//计算联通块的数量
{
count++;
}
}
cout<<count<<endl;
int flag=;
for(int i=;i<=n;i++)
{
if(p[i]==i)
{
if(flag==)cout<<" ";
flag=;
cout<<sum[i];
}
}
cout<<endl;
}
return ;
}
这个题目利用DFS求解也可以。
要建立一个二维数据，将要连接点的点连在一起，并且用一个一位数据记录每个点是否被搜索过；
代码如下：
#include<iostream>
#include<cstring>
using namespace std;
const int maxn=;
int map[maxn][maxn];
int vis[maxn];
int tot;
int n,m;
void dfs(int s)
{
tot++;
vis[s]=;
for(int i=;i<=n;i++)
if(!vis[i]&&map[s][i])//当从1到n都搜索一遍后 变会自动停止
{
dfs(i);
}
}
int main()
{
int now=;
int v,u;
while(cin>>n>>m)
{
tot=;
now=;
int sum[maxn];
memset(map,,sizeof(map));
memset(vis,,sizeof(vis));
for(int i=;i<=m;i++)
{
scanf("%d%d",&u,&v);
map[u][v]=map[v][u]=;
}
for(int i=;i<=n;i++)
{
if(vis[i]==)
{
tot=;
dfs(i);
sum[++now]=tot;
}
}
cout<<now<<endl;
for(int i=;i<=now;i++)
{
if(i>)cout<<" ";
cout<<sum[i];
}
cout<<endl;
}
return ;
} 利用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]=;
while(!Q.empty())
{
int u=Q.front();Q.pop();
total++;
for(int i=;i<=n;i++)
{
if(map[u][i]&&!mk[i])
{
mk[i]=;
Q.push(i);
}
}
}
}
int main()
{
int u,v;
int now=;
while(scanf("%d%d",&n,&m)==)
{
now=;
memset(map,,sizeof(map));
memset(mk,,sizeof(mk));
for(int i=;i<=m;i++)
{
scanf("%d%d",&u,&v);
map[u][v]=map[v][u]=;
}
for(int i=;i<=n;i++)
{if(mk[i]==)
{
total=;
bfs(i);
sum[++now]=total;
}
}
cout<<now<<endl;
for(int i=;i<=now;i++)
{
if(i>)cout<<" ";
cout<<sum[i];
}
cout<<endl;
}
return ;
}
以上三个方法，都是比较容易理解上手的，能够很好的提高做类似题目的能力；