并查集解决方案的详解
在说并查集之前，我们需要先来了解使用并查集的背景知识：等价类。 我们先来看看等价关系的概念：假定有一个具有n个元素的集合U=1,2,3…,n和一个具有r个关系的集合R=(i1,j1)(i2,j2)(i3,j3)…(ir,jr)，当满足： 1.自反： 对于所有的a属于U，有(a,a)属于R； 2.对称： 对于(a,b)属于R，当且仅当(b,a)属于R； 3.传递： 若(a,b)属于R且(b,c)属于R，则有(a,c)属于R。 我们说R是一个等价关系。而在一个等价关系中，若(a,b)属于R，则元素a,b等价。而所谓等价类是指相互等价的最大集合，而这就意味着不存在类以外的元素与类内部的元素等价。（一个元素只属于一个等价类）也就相当于把集合U划分为若干个不相交的等价类。 但是，等价类有两个不同的分类，分为离线等价类与在线等价类。离线等价类自不必说，每个元素只属于一个等价类，但是在线等价类问题中，初始时，每个元素都属于一个独立的等价类，那我们衍生出了一些操作：合并，查找，这就是我们的并查集问题的由来。
数组是最简单的解决方法，我们创建一个数组，使得数组标号的等价类就是它本身，例如a[i]就属于等价类i，合并时就将其元素改成另一元素的值，查找时就输出数组内的元素。 代码也很简单：
int *equivClass;//等价类数组 int n;//元素个数 void initialize(int numberOfElement)//初始化 { n = numberOfElement; equivClass = new int[n+1]; for(int i = 1;i<=n;i++) equivClass[i] = i; } void unite(int classA,int classB)//合并 { for(int i = 1;i<=n;i++) if(equivClass[i] == classB) equivClass[i] = classA; } int find(int theElement)//查找 { return equivClass[theElement]; } int main() { initialize(10); unite(1,4); unite(2,7); unite(1,2); for(int i = 1;i<=10;i++) cout<<i<<"的等价类:"<<find(i)<<endl; }程序运行的结果就在这里了，将1,2,4,7合并。 这种解决方法简单易懂，但是我们从复杂度上来讲，我们初始化数组复杂度为Q(n),合并的复杂度也为Q(n)，find函数的复杂度为Q(1)，但是综合来讲，复杂度未免有些大，那我们引入第二种解决方案。
如果将等价类作为一个链表，那么合并操作的复杂度就可大大降低为常数级，在一个等价类中，可以沿着链表的指针找的所有的元素，无需去检查所有的值。但是，如果用链表来解决，我们的find函数的复杂度就会提高，我们需要遍历链表。由此，我们想到了将数组的优势与链表的优势结合起来，通过使用整型指针来解决（也称之为模拟指针）。 那么首先我们来构造模拟指针的结构(struct)： 首先，我们的结构中需要等价类的标识符，等价类的大小，以及指向下一个等价类元素的指针。 代码如下：
struct equivNode { int equivClass;//元素类标识符 int size;//类的元素个数 int next;//下一个元素指针 };这样一来，我们就得到了比较简略的结构。 那么我们要实现数组与链表的结合，我们只需要构造节点类型的数组即可，我们就可以按索引来查找等价类。
equivNode *node;//节点的数组 int n;//元素个数那么，基本的工作完成，接下来该考虑解决并查集的问题了。 当我们合并等价类是，我们为了尽量降低时间复杂度，我们采用将小的等价类合并到大的等价类中，并将小等价类插入到大等价类的头结点后（为了降低程序的时间复杂度，优化代码）。 接下来我们看看完整的代码：
struct equivNode { int equivClass;//元素类标识符 int size;//类的元素个数 int next;//下一个元素指针 }; equivNode *node;//节点的数组 int n;//元素个数 void initialize(int numberOfElements)//初始化 { n = numberOfElements; node = new equivNode[n+1]; for(int i = 1;i<=n;i++) { node[i].equivClass = e; node[i].next = 0; node[i].size = 1; } } void unite(int classA,int classB)//合并 { if(node[classA].size>node[classB].size) swap(classA,classB); int i; for(i = classA;node[i].next!=0;i=node[i].next) node[i].equivClass = classB; node[i].equivClass = classB; node[classB].size += node[classA].size; node[i].next = node[classB].next; node[classB].next = classA; } void find(int theElement)//查找 { return node[theElement].equivClass; }至此我们所采用的模拟指针的方案告一段落，但是我们依旧不满意，我们合并操作的复杂度依然没有降低，所以，前两种方案虽然简单，但是效率不高，那么我们给出第三种方案。
这是一块不同于以上解决方案的知识点，我们先来看一看一个集合的树形的描述：我们将一个节点代表一个元素，任何一个元素都可以代表根节点，剩余元素的任何子集都可以作为根元素的孩子，在剩余的元素可以作为根元素的孙子… 我们如果要实现并查集，我们的求解策略是将每一个等价类表示为一个数。在这里，我们要用到上边用到的虚拟指针，，而且我们用到的是数的链表描述。但这里，我们的实现方法与树有些不同，我们是从某个节点得到其所在的等价类，也就是说从子节点指向父节点。我们的每个节点需要一个父域，域内的数字我们采用整型数。 我们来看看代码：
int *parent; void initialize(int numberOfElements) { parent = new int[numberOfElements+1]; for(int i = 1;i<=numberOfElements;i++)//初始化 parent[i] = i; } void unite(int rootA,int rootB) { parent[rootB] = rootA; } int find(int theElement) { while (parent[theElement] != 0) theElement = parent[theElement]; return theElement; }在这种数据结构中，我们可以看到，合并函数unite()的复杂度降到了Q(1)，查找函数find的复杂度为Q(h)，h为树的高度，均为常数级的复杂度，效率相比前两种大大提高。
学艺不精，可能未完，待续…
