查并集

引导问题:

任务:

在某个城市里住着n个人,现在给定关于这n个人的m条信息(每条信息格式A,B,表示A和B认识)。

假设所有认识的人一定属于一个单位,请计算该城市最多有多少单位。

Sample Input:

n=5;m=3;

1 2

3 4

2 5

Sample Output:

2

什么是并查集?

英文:Disjoint Set, 即“不相交集合”;

问题描述:将编号分别为1…N的N个对象划分为不相交集合,在每个集合中,选择其中某个元素代表所在集合。

常见两种操作:

  • 合并两个集合
  • 查找元素属于那个集合

实现方法(1)

  • 用编号最小的元素标记所在集合;

  • 定义一个数组Set[1..n],其中Set[i]表示元素i所在的集合;

    ​ set(i) 1 |2 |1 |4 |2 |6 |1 |6 |2 |2

    ​ i 1 2 3 4 5 6 7 8 9 10

    不相交集合:{==1==,3,7} ,{==4==}, {==2==,5,9,10},{==6==,8}

  • 查找

1
2
3
4
find1(x)
{
return Set[x];
}
1
2
3
4
5
6
7
8
9
10
Mergel(a,b)
{
i=min(a,b);
j=max(a,b);
for(k=l;k<=N;k++)
{
if(Set[k]==j)
Set[k]=i;
}
}

实现方法(2)

  • ·每个集合用一棵“有根树”表示

    • 定义数组Set[1,..n]

    • Set[i]=i,则i表示本集合,并是集合对应树的根

    • Set[i]=j,若j不等于i,则j是i的父节点

      Set(i) 1 | 2 | 3 | 2 | 1 | 3 | 4 | 3 | 3 | 4 |

      ​ i 1 2 3 4 5 6 7 8 9 10

1
2
3
4
5
6
7
find2(x)
{
r=x;
while(Str[r]!=r)
r=Set[r];
return r;
}
1
2
3
4
merge2(a.b)
{
Set[a]=b;
}
  • 如何避免最坏情况

    方法:将深度小的树合并到深度大的树

    实现:假设两棵树的深度分别为h1和h2,则合并后的树的高度h是:

    ​ max(h1,h2), if h1<>h2

    ​ h1+1, if h1=h2

    效果:任意顺序的合并操作以后,包含k个节点的树的最大高度不超过[lg k]