将多個集合合并成沒有交集的集合。
給定一個字元串的集合，格式如：{aaa bbb ccc}， {bbb ddd}，{eee fff}，{ggg}，{ddd hhh}要求将其中交集不為空的集合合并，要求合并完成後的集合之間無交集，例如上例應輸出{aaa bbb ccc ddd hhh}，{eee fff}， {ggg}。
（1）請描述你解決這個問題的思路；
（2）請給出主要的處理流程，算法，以及算法的複雜度
（3）請描述可能的改進。
2、分析
1. 假定每個集合編号為0，1，2，3...
2. 建立一個hash_map，key為字元串，value為一個連結清單，連結清單節點為字元串所在集合的編号。周遊所有的集合，将字元串和對應的集合編号插入到hash_map中去。
3. 建立一個長度等于集合個數的int數組，表示集合間的合并關系。例如，下标為5的元素值為3，表示将下标為5的集合合并到下标為3的集合中去。開始時将所有值都初始化為-1，表示集合間沒有互相合并。在集合合并的過程中，我們将所有的字元串都合并到編号較小的集合中去。
周遊第二步中生成的hash_map，對于每個value中的連結清單，首先找到最小的集合編号（有些集合已經被合并過，需要順着合并關系數組找到合并後的集合編号），然後将連結清單中所有編号的集合都合并到編号最小的集合中（通過更改合并關系數組）。
4.現在合并關系數組中值為-1的集合即為最終的集合，它的元素來源于所有直接或間接指向它的集合。
0: {aaa bbb ccc}
1: {bbb ddd}
2: {eee fff}
3: {ggg}
4: {ddd hhh}
生成的hash_map，和處理完每個值後的合并關系數組分别為
aaa: 0
bbb: 0, 1
ccc: 0
ddd: 1, 4
eee: 2
fff: 2
ggg: 3
hhh: 4
是以合并完後有三個集合，第0，1，4個集合合并到了一起，
第2，3個集合沒有進行合并。
例題：現在有n個學生，屬于m個group，學生編号為0~n-1，學生0被認為是一個suspect，和學生0在一個group的學生都被認為是suspects，求出suspects的值。以下輸入表示：
100表示：100個學生；4表示：4個group；下面每一行表示一個group，第一個數字表示group中學生數目，接着是具體的學生編号。
Sample Input
100 4
2 1 2
5 10 13 11 12 14
2 0 1
2 99 2
200 2
1 5
5 1 2 3 4 5
1 0
0 0 Code
#include<iostream>
using namespace std;
int n, m, i, j;
int father[30005], num[30005];
void makeSet(int n)
{
for(i = 0; i < n; i++)
{
father[i] = i; //使用本身做根
num[i] = 1;
}
}
int findSet(int x)
{
if(father[x] != x) //合并後的樹的根是不變的
{
father[x] = findSet(father[x]);
return father[x];
void Union(int a, int b)
int x = findSet(a);
int y = findSet(b);
if(x == y)
return;
if(num[x] <= num[y])
father[x] = y;
num[y] += num[x];
else
father[y] = x;
num[x] += num[y];
int main()
while(scanf("%d %d", &n, &m)!=EOF && n != 0)
makeSet(n);
for(i = 0; i < m; i++)
{
int count, first, b;
scanf("%d %d",&count, &first);
for(j = 1; j < count; j++)
{
scanf("%d",&b);
Union(first,b);
}
}
printf("%d\n",num[findSet(0)]);
return 0;