不相交集（disjointset）是一个经典的数据结构，它有三种操作：Make-set(a)：生成一个包含元素a的集合S；Union(X,Y)：合并两个集合X和Y；Find-set(a)：找到元素a所在的集合S，即通过元素找到集合句柄；非常适合解决集合的合并和查找问题，也常被称为归并查找集。1、并查表的链表实现如上图所示，并查表可以通过链表来实现。(1)链表实现的联合搜索集中Find-set(a)的时间复杂度是多少？集合中的每一个元素都指向“集合的句柄”，这样就可以“找到元素a所在的集合S”，即Find-set(a)操作在O(1）时间。(2)用链表实现union(X,Y)的时间复杂度是多少？假设有一个集合：S1={7,3,1,4}S2={1,6}合并S1和S2一个集合需要做两件事：第一个集合的尾元素链接到第一个集合的头元素第二个系列（蓝线1）；第二个集合的所有元素都指向第一个集合的句柄（蓝线2,3）；合并的效果是：变成了一个更大的集合S1。合并集合时，将短链表连接到长链表，这样改变的元素更少。这种优化称为“加权合并”。画外音：在实现过程中，集合句柄需要存储元素个数、头元素、尾元素等属性，方便上面的操作。假设每个集合的平均元素个数为n，则Union(X,Y)运算的时间复杂度为O(n)。(3)Find-set(a)和Union(X,Y)能否在O(1)时间内完成？是的，这就引出了联合查找的第二种实现方式。2.联合搜索的有根树的实现(1)什么是有根树，它和普通树有什么区别？常用的set是用普通的二叉树实现的，其元素的数据结构为：element{intdata;element*left;element*right;}通过左指针和右指针，父节点指向子节点。对于有根树，其元素的数据结构为：element{intdata;element*parent;}通过子节点指向父节点。假设有一个集合：S1={7,3,1,4}S2={1,6}如果用有根树表示，可能是这样的：所有元素都通过父指针指向集合句柄,而所有元素Find-set(a)的时间复杂度也是O(1)。画外音：假设集合的第一个元素代表集合句柄。(2)有根树实现union(X,Y)的过程是怎样的？时间复杂度是多少？通过有根树实现并集。合并集合时，直接将一个集合句柄指向另一个集合句柄即可。如上图，S2的句柄指向S1的句柄，集合合并完成：S2死了，S1变成了更大的集合。很容易知道集合合并的时间复杂度是O(1)。会发现集合合并后，有根树的高度变高了，类似于“加权合并”的优化思路。节点数少的有根树总是指向节点数多的有根树（更准确的说，是高度矮的树，指向高度高的树），这种优化称为“按等级合并”。(3)出现了新的问题。集合合并后，并不是所有元素的Find-set(a)操作都是O(1)。我应该怎么办？如S1和S2合并后的新S1所示，***“通过元素6找到新S1的句柄”，O(1)时间无法完成，需要两次操作。但是，为了让以后的“通过元素6找到新S1的句柄”的操作能够在O(1)时间内完成，在最后执行Find-set("6")时，需要findtherootofelement6》路径上的所有元素都指向集合句柄，如下图所示。如果一个元素不直接指向集合句柄，则路径上的所有元素在执行过程中都会直接指向集合句柄***Find-set(a)操作，这种优化称为“路径压缩”。画外音：当路径上的元素第二次执行Find-set(a)时，时间复杂度为O(1)。之后实施“路径压缩”优化，Find-set的平均时间复杂度依然是O(1)结论通过链表实现和搜索：Find-set的时间复杂度是O(1)常数时间Union的时间复杂度是集合中元素的平均个数，即线性时间画外音：别忘了“加权合并”优化。通过有根树实现联合查找：联合的时间复杂度为O(1)常数时间。Find-set的时间复杂度通过“按rank合并”和“路径压缩”进行了优化，平均时间复杂度也是O(1)使用和搜索，非常适合解决“微信群覆盖”的问题.想法比结论更重要，能有所收获就好。【本文为专栏作者《58神剑》原创稿件，转载请联系原作者】点此阅读更多该作者好文
