联通块是指给定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个点看成独立的联通块，然后每个每个独立的联通块都有一个节点，然后每次连接两个点，就将它们的节点加在一起；
代码如下：
1 #include<iostream> 2 #include<cstring> 3 using namespace std; 4 const int maxn=1010; 5 int p[maxn];//作为每个独立的点 6 int sum[maxn];//每个节点下面连接的点 7 int find(int x) 8 { 9 if(x==p[x])return x; 10 return p[x]=find(p[x]);//压缩路径 11 } 12 int main() 13 { 14 int n,m; 15 while(cin>>n>>m) 16 { 17 if(n==0)//如果没有数据那就直接按照格式输出零 ，一般不会有这种输入 18 { 19 cout<<0<<endl<<0<<endl; 20 continue; 21 } 22 for(int i=1;i<=n;i++)//初始化，令每一个点成为独立的联通块 23 { 24 p[i]=i; 25 sum[i]=1;//每个联通块中节点的个数为 1 26 } 27 28 int a,b; 29 for(int i=1;i<=m;i++) 30 { 31 cin>>a>>b; 32 int fa=find(a);//查找a的头节点 33 int fb=find(b);//查找b的头节点 34 if(fa!=fb)//如果头节点不同 35 { 36 p[fa]=fb;//将两个点合并 37 sum[fb]+=sum[fa];//并且使新头节点中的个数加上新连接的联通块所含节点的个数 38 } 39 } 40 int count=0; 41 for(int i=1;i<=n;i++) 42 { 43 if(p[i]==i)//计算联通块的数量 44 { 45 count++; 46 } 47 } 48 cout<<count<<endl; 49 int flag=0; 50 for(int i=1;i<=n;i++) 51 { 52 if(p[i]==i) 53 { 54 if(flag==1)cout<<" "; 55 flag=1; 56 cout<<sum[i]; 57 } 58 } 59 cout<<endl; 60 } 61 return 0; 62 }
这个题目利用DFS求解也可以。
要建立一个二维数据，将要连接点的点连在一起，并且用一个一位数据记录每个点是否被搜索过；
代码如下：
1 #include<iostream> 2 #include<cstring> 3 using namespace std; 4 const int maxn=1000; 5 int map[maxn][maxn]; 6 int vis[maxn]; 7 int tot; 8 int n,m; 9 void dfs(int s) 10 { 11 tot++; 12 vis[s]=1; 13 for(int i=1;i<=n;i++) 14 if(!vis[i]&&map[s][i])//当从1到n都搜索一遍后 变会自动停止 15 { 16 dfs(i); 17 } 18 } 19 int main() 20 { 21 int now=0; 22 int v,u; 23 while(cin>>n>>m) 24 { 25 tot=0; 26 now=0; 27 int sum[maxn]; 28 memset(map,0,sizeof(map)); 29 memset(vis,0,sizeof(vis)); 30 for(int i=1;i<=m;i++) 31 { 32 scanf("%d%d",&u,&v); 33 map[u][v]=map[v][u]=1; 34 } 35 for(int i=1;i<=n;i++) 36 { 37 if(vis[i]==0) 38 { 39 tot=0; 40 dfs(i); 41 sum[++now]=tot; 42 } 43 } 44 cout<<now<<endl; 45 for(int i=1;i<=now;i++) 46 { 47 if(i>1)cout<<" "; 48 cout<<sum[i]; 49 } 50 cout<<endl; 51 } 52 return 0; 53 } 54 55 利用BFS做也是比较方便的； 56 57 利用队栈保存每次搜索到的数据，并且在处理完成它的子节点后删除；同时利用一个数组记录是否拜访过它； 58 59 #include <cstdio> 60 #include <cstring> 61 #include<iostream> 62 #include <queue> 63 using namespace std; 64 #define N 100 65 int n,m; 66 int map[N][N]; 67 int mk[N]; 68 int sum[N]; 69 int total; 70 void bfs(int s) 71 { 72 queue <int> Q; 73 Q.push(s); 74 mk[s]=1; 75 while(!Q.empty()) 76 { 77 int u=Q.front();Q.pop(); 78 total++; 79 for(int i=1;i<=n;i++) 80 { 81 if(map[u][i]&&!mk[i]) 82 { 83 mk[i]=1; 84 Q.push(i); 85 } 86 } 87 } 88 } 89 int main() 90 { 91 int u,v; 92 int now=0; 93 while(scanf("%d%d",&n,&m)==2) 94 { 95 now=0; 96 memset(map,0,sizeof(map)); 97 memset(mk,0,sizeof(mk)); 98 for(int i=1;i<=m;i++) 99 { 100 scanf("%d%d",&u,&v); 101 map[u][v]=map[v][u]=1; 102 } 103 for(int i=1;i<=n;i++) 104 {if(mk[i]==0) 105 { 106 total=0; 107 bfs(i); 108 sum[++now]=total; 109 } 110 } 111 cout<<now<<endl; 112 for(int i=1;i<=now;i++) 113 { 114 if(i>1)cout<<" "; 115 cout<<sum[i]; 116 } 117 cout<<endl; 118 } 119 return 0; 120 }
以上三个方法，都是比较容易理解上手的，能够很好的提高做类似题目的能力；