一分钟说清楚并查集

分离集合(disjoint set)是一种经典的数据结构，它有三类操作：

Make-set(a)：生成包含一个元素a的集合S；

Union(X, Y)：合并两个集合X和Y；

Find-set(a)：查找元素a所在集合S，即通过元素找集合句柄；

它非常适合用来解决集合合并与查找的问题，也常称为并查集。

一、并查集的链表实现

如上图，并查集可以用链表来实现。

链表实现的并查集，Find-set(a)的时间复杂度是多少？

集合里的每个元素，都指向“集合的句柄”，这样可以使得“查找元素a所在集合S”，即Find-set(a)操作在O(1)的时间内完成。

链表实现的并查集，Union(X, Y)的时间复杂度是多少？

假设有集合：

S1={7,3,1,4}

S2={1,6}

合并S1和S2两个集合，需要做两件事情：

(1) 第一个集合的尾元素，链向第二个集合的头元素(蓝