并查集（Disjoint Set）

并查集（Disjoint Set）2014-12-10 cnblogs codingwu在一些有N个元素的集合应用问题中，我们通常是在开始时让每个元素构成一个单元素的集合，然后按一定顺序将属于同一组的元素所在的集合合并，其间要反复查找一个元素在哪个集合中。这一类问题其特点是看似并不复杂，但数据量极大，若用正常的数据结构来描述的话，往往在空间上过大，计算机无法承受；即使在空间上勉强通过，运行的时间复杂度也极高，根本就不可能在规定的运行时间（1～3秒）内计算出试题需要的结果，只能用并查集来描述。

定义

并查集（Disjoint Set），即“不相交集合”，是一种树型的数据结构，用于处理一些不相交集合（Disjoint Sets）的合并及查询问题。常常在使用中以森林来表示。集就是让每个元素构成一个单元素的集合，也就是按一定顺序将属于同一组的元素所在的集合合并。

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

常见两种操作：

合并两个集合

查找某元素属于哪个集合

用编号最小的元素标记所在集合；定义一个数组 set[1..n] ，其中set[i] 表示元素i 所在的集合；

算法实现

查找 Θ（1）

find1（x）{return set[x];}

合并 Θ（N）

Merge1（a,b）{ i = min（a,b）;j = max（a,b）;for （k = 1; k <= N; k++） {if （set[k] == j）set[k] = i;}}

对于“合并操作”，必须搜索全部元素！有没有可以改进的地方呢？