并查集并查集

等价关系关系R是描述集合S每对元素（a，b），a R b是真或者假，假如a R b是真的，那么我们说a关联于b。而一个等价关系需要满足以下三个特征：

自反
对称
传递
比如<=就不是等价关系，因为它不满足对称性; 电气连接、城市连接显而易见都是等价的。

动态等价关系问题给定一个定价关系，对于任意的a和b判断a是否b。假如这个关系存储在一个二维的布尔类型的数组中，这样就可以线性的解决，但问题这种关系往往不是显性而是隐性的。
举一个例子，假设一个有5个元素的集合{a1，a2，a3，a4，a5}，这样就有25对元素，每一个和另外一个有或者没有关联。当我们知道a1 ~ a2，a3 ~ a4，a5 ~ a1，a4 ~ a2，这也意味着所有的组对都是关联的，这个很好推断。
元素a的等价类是包含所有元素S的子集和a有关联的所有元素，等价类是S的一个分区，S中的每一个成员也必然准确的出现在一个等价类中。通过检查a和b是否在同一个等价类中来拍判断a~b。
通常输入开始是只有一个元素的N个集合，代表了刚开始所有的元素是没有关联的。每一个集合有不同的元素，Si和Sj的交集为空，称为不相交集。
有两个比较显而易见的操作，首先是find，它会返回给定一个元素的等价类，然后是添加关联操作，假如我们要添加关系a~b，我们首先需要看a和b是否已经关联，可以通过finds操作来检查a和b是否有相同的等价类。假如他们没有，我们执行union操作，这个操作合并包含a的等价类和b的等价类到一个等价类中。我们可以通过以下代码来实现

public class DisjSets { private int[] s; public DisjSets(int numElements) { s = new int[numElements]; for(int i = 0; i < s.length; i++) { s[i] = -1; }}public void union(int root1, int root2) { s[root2] = root1; }public int find(int x) { if(s[x] < 0) { return x; } else { return find(s[x]); } } }

当然以上实现比较随意，就是将第二个树作为第一个树的子树。一个简单的提升是通常让小的树作为大的树的子树，也通常被称为union-by-size。另外一种方法监控每一个子树的深度，尽量使深度越浅越好，只有当两个等价树相交时才会增加深度。我们通常使深度初始位-1，并存储深度的负值。如以下代码所示:

public void union(int root1, int root2) { if(s[root2] < s[root1]) { s[root1] = root2; } else { if(s[root1] == s[root2]) { s[root1]--; } s[root2] = root1; } }

【并查集】union/find算法在大多数时候都是可以被接受的，通过上面我们优化了union算法，那么对于find算法比较有名的操作是路径压缩，比如执行find(x),路径压缩就是从x到root节点的每一个节点将他们的父节点改为root节点。代码如下: