并查集：使用集合中某個元素來代表這個集合，這個集合組織成樹狀結(jié)構(gòu)，所有元素指向根節(jié)點(diǎn)。
（1）維護(hù)一個數(shù)組，用于存儲每個節(jié)點(diǎn)的父親索引。
（2）主要涉及到三個操作：
? ? ? ? ? （1）makeSet（int size）：初始化集合，此時每個集合擁有一個元素，該元素指向自己。
? ? ? ? ? （2）find（int x）：找到x所在集合的代表元，常用來判斷兩個元素是否處于同一集合。
? ? ? ? ? ?（3）union（int x，int y）：合并x和y所在的集合，此時將一個根節(jié)點(diǎn)懸掛在另一個根節(jié)點(diǎn)下。具體的合并策略包括根據(jù)樹的高度合并或者根據(jù)樹包含的元素個數(shù)合并。
public void makeSet（int ?size）{
? ? ? ? ? ? for （int i=0；i<size ； i++）
? ? ? ? ? ? ? ? ? ?unset[i] = i; ? ? ? //每個元素都是父親
}
public int find(int x){
? ? ? ? ?if(x!=unset[x])
? ? ? ? ? ? ? ?unset[x]=find(unset[x]); ?//路徑壓縮，所有該條路線上的節(jié)點(diǎn)都指向根節(jié)點(diǎn)
? ? ? ? ?return unset[x];
}
public void union (int x,int y){
? ? ? ?if((x=find(x)==(y=find(y))) return; ? ? ? ? ?//x和y處于同一集合
? ? ? ?if(rank[x]>rank[y]) ? ? ?{ ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? //維護(hù)一個rank數(shù)組，記錄高度，每次加入高度低的樹
? ? ? ? ? ?unset[y]=x;
? ? ? ?}else{
? ? ? ? ? unset[x]=y;
? ? ? ? ? if(rank[x]==rank[y]) ? ? rank[y]++; ? ? ? ? ? ?//更新樹的高度
}
第二種設(shè)計(jì)：只需要維護(hù)一個unset數(shù)組，如果數(shù)組的值為正數(shù)，那么表示父親節(jié)點(diǎn)的索引；如果數(shù)組的值為負(fù)數(shù)，那么表示該節(jié)點(diǎn)為根節(jié)點(diǎn)，負(fù)數(shù)的相反數(shù)表示樹的元素個數(shù)。
public int find(int x){
? ? ? if(unset[x]<0) ? return x;
? ? ? unset[x]=find(unset[x]);
? ? ? return unset[x];
}
public void makeSet(int size){
? ? ?for(int i=0;i<size;i++)?
? ? ? ? ? unset[i]=-1;
}
public void union(int x,int y){
? ? ? if((x=find(x))==(y=find(y))) return;
? ? ? if(unset[x]<unset[y]){
? ? ? ? ? ?unset[x]+=unset[y];
? ? ? ? ? ?unset[y]=x;
? ? ? ?}else{
? ? ? ? ? ? unset[y]+=unset[x];
? ? ? ? ? ? unset[x]=y;
? ? ? ?}
}
