并查集解决的问题？
- 连接问题：并查集可以很好的解决网络中的连接状态。网络指的是很多的个体，个体之间可能存在关系。并查集就可以很好的来表示这个网络的状态。
- 集合操作：另外，并查集还很好的解决数学中的集合操作，比如求两个结合的相同部分和和并两个集合。
package 并查集;
/**
* 并查集
*/
public class UnionFind {
private int[] parent;//保存父节点信息
private int[] rang;//保存节点的等级信息，当合并的时候会有作废信息产生
private int size;
/**
*
* @param size
*/
public UnionFind(int size){
parent = new int[size];
this.size=size;
for(int i=0;i<size;i++){
parent[i]=i;
rang[i]=1;
}
}
/**
* 判断是否连接
* @param p
* @param q
* @return
*/
boolean isConnected(int p,int q){
return find(p)==find(q);
}
/**
* 合并
* @param p
* @param q
*/
public void union(int p,int q){
int pp= find(p);
int pq=find(q);
if(pp==pq){
return;
}
int rangp= rang[p];
int rangq= rang[q];
if(rangp>rangq){
parent[pq]=pp;
}else if(rangp<rangq){
parent[pp]=pq;
}else {
parent[pq]=parent[pp];
rang[pq]++;
}
}
/**
* 查找，这里使用了路径压缩
* @param p
* @return
*/
public int find(int p){
if(parent[p]!=p){
parent[p]=find(parent[p]);
}
return p;
}
}
