我们希望它的算法复杂度达到O(1)，那么具体应该如何实现呢？
并查集是一类树状结构，非双向，所以在实现union中应该先实现find()，因为并的两个元素可能因为从属关系已经相并，或者二者是另外一个大集合的元素。
在实现查操作（find）时，我们维护一个id[]数组用以存储每个点的label属性，使用find时将对返回对应点的对应id，同时对于实现并操作时必须满足维护id[]数组这个条件
成本：在实现unionfind算法时，其成本可视为访问id[]数组的次数。
代码如下：
public int find(int p){ //find的速度会非常的快 return id[p]; } public void union(int p, int q){ //union需要进行遍历，相对来说会比较慢 if(find(p) == find(q)) return; for(int i = 0 ; i < id.length ; i++){ if(id[i] == find(p)) //这里应该先将p的id计算出来效率会比较快 id[i] = find(q); } count--; }**分析：**find的速度会非常的快，但是Quick-Find算法无法面对较大的集合，因为每一次使用Union时都需要对原数组进行一次扫描，其复杂度至少是O（N**2）——>（N+3的单次调用乘上N-1次的最坏情况下调用）
所以我们提出Quick-Union
代码如下
private int find(int p){ while(p != id[p]){ p = id[p]; //查找根节点 } return p; } void Union(int p , int q){ int pRoot = find(p); int qRoot = find(q); if(pRoot == qRoot){ return; } id[pRoot] = qRoot; count --; }分析：在这种QuickUnion的情况下，存储形式的树形结构被强调了，每个点的id存放的是它父节点的位置，这样的Union方法会快上很多，同时Connected()方法也需要遍历到根节点再进行对比。 同时Find方法的时间复杂度为N，M对Find的复杂度为o(N*M)—->find总是会遍历一棵树，可能这棵树太大太大
所以我们提出加权的Quick-Union方法，在这个算法中我们总是把小树连接到大树上
为了实现加权的QU，我们需要定义几个新的变量，代码如下
private int[] size; private int[] id; WeightQuickUnionUF(int N){ count = N; id = new int[N]; size = new int[N]; for(int i = 0 ; i <N ; i ++){ id[i] = i; } for(int i = 0 ; i < N ; i++){ size[i] = 1; } } public int find( int p){ while(p != id[p]) p = id[p]; return p; } public void union(int p , int q){ int i = find(p); int j = find(q); if(i == j) return; if(size[i] < size[j]){ id[i] = i; size[j] += size[i]; } else{ id[j] = i; size[i] += size[j]; } count --; }复杂度MlgN
为了实现O（1）的均摊复杂度，可以在每次Union时对路径进行压缩，尽量缩短树的度，这里提供这个思路，各位水友自行解决吧~
最后转载个特别好玩的并查集思路
为了解释并查集的原理，我将举一个更有爱的例子。 话说江湖上散落着各式各样的大侠，有上千个之多。他们没有什么正当职业，整天背着剑在外面走来走去，碰到和自己不是一路人的，就免不了要打一架。但大侠们有一个优点就是讲义气，绝对不打自己的朋友。而且他们信奉“朋友的朋友就是我的朋友”，只要是能通过朋友关系串联起来的，不管拐了多少个弯，都认为是自己人。这样一来，江湖上就形成了一个一个的群落，通过两两之间的朋友关系串联起来。而不在同一个群落的人，无论如何都无法通过朋友关系连起来，于是就可以放心往死了打。但是两个原本互不相识的人，如何判断是否属于一个朋友圈呢？我们可以在每个朋友圈内推举出一个比较有名望的人，作为该圈子的代表人物，这样，每个圈子就可以这样命名“齐达内朋友之队”“罗纳尔多朋友之队”……两人只要互相对一下自己的队长是不是同一个人，就可以确定敌友关系了。但是还有问题啊，大侠们只知道自己直接的朋友是谁，很多人压根就不认识队长，要判断自己的队长是谁，只能漫无目的的通过朋友的朋友关系问下去：“你是不是队长？你是不是队长？”这样一来，队长面子上挂不住了，而且效率太低，还有可能陷入无限循环中。于是队长下令，重新组队。队内所有人实行分等级制度，形成树状结构，我队长就是根节点，下面分别是二级队员、三级队员。每个人只要记住自己的上级是谁就行了。遇到判断敌友的时候，只要一层层向上问，直到最高层，就可以在短时间内确定队长是谁了。由于我们关心的只是两个人之间是否连通，至于他们是如何连通的，以及每个圈子内部的结构是怎样的，甚至队长是谁，并不重要。所以我们可以放任队长随意重新组队，只要不搞错敌友关系就好了。于是，门派产生了。 来自http://www.cnblogs.com/TonyNeal/p/bingchaji.htmlUPDATE！最近研究了下路径压缩，然后写了下面的代码
package UF; import edu.princeton.cs.introcs.StdOut; public class UF_sample_3 { /** * now we try to make the Quick-Union tree more short * * Modify quick-union to avoid tall trees * * Keep track of size of each tree(number of object) * * Balance by ** linking root of smaller tree to roof of large trss. ** * * WEIGHT UNION * * Initialized N * * Union lgN ↑ * * Connected lgN */ public int[] sz ; //size tree to store the number of son that every roots have public int[] id ; public int count ; public UF_sample_3(int n){ id = new int[n]; sz = new int[n]; count = n ; for(int i = 0 ; i < n ; i++){ id[i] = i ; sz[i] = 1 ; } } public int getRoot(int num){ while(num!=id[num]){ id[num] = id[id[num]]; //这里是关键哦！ num = id[num]; } return num ; } public void union(int num1 , int num2){ int pid = getRoot(num1) ; int qid = getRoot(num2) ; if(sz[pid] < sz[qid]){id[pid] = qid ; sz[qid] = sz[qid] + sz[pid];} else{id[qid] = pid ; sz[pid] = sz[qid] + sz[pid];} } public boolean connected(int num1 , int num2){ if(getRoot(num1) == getRoot(num2)){ StdOut.println(num1 + ","+ num2 + " they are connected"); return true; } else { StdOut.println(num1 + ","+ num2 + " they are not connected"); return false; } } public void println(){ StringBuilder str = new StringBuilder(); for(int i = 0 ; i < count ; i++){ str.append(id[i] +","); } StdOut.println(str.toString()); } public static void main(String[] args) { // TODO Auto-generated method stub UF_sample_3 uf = new UF_sample_3(10); uf.union(4, 3); uf.println(); uf.union(3, 8); uf.println(); uf.union(6, 5); uf.println(); uf.union(9, 4); uf.println(); uf.union(2, 1); uf.println(); uf.union(8, 9); uf.println(); uf.connected(5, 0); uf.union(5, 0); uf.connected(5, 0); uf.println(); uf.union(7, 2); uf.println(); uf.union(6, 1); uf.println(); uf.union(7, 3); uf.println(); } }大家自己试试吧，关键的那段代码我已经标注了~
