数据结构方面，你了解并查集么？
上交05年计算机复试 上机 畅通工程问题：
例题1 修路连通问题 某省调查城镇交通状况，得到现有城镇道路统计表，表中列出了每条道路直接连通的城镇。省政府“畅通工程”的目标是使全省任何两个城镇间都可以实现交通（但不一定有直接的道路相连，只要互相间接通过道路可达即可）。问最少还需要建设多少条道路？
本质可以理解成图论的连通分支 个数问题，只有一个连通分支，那么 点点互通，两个连通分支，那么需要一条路，。。。。。。
如果用计算机编程实现的话，可能有回路，很多节点，很多边，如何实现呢？那么就引出了并查集！
并查集由一个整数型的数组和两个函数构成。数组father[ ]记录每个点的前导点，函数 find 查找根节点，mix 合并。
- int father[ ] 数组，记录上级领导。//分别记录了n个节点中，每一个点所在集群（连通分支）的上一级节点，每个节点需要一层层查询自己的根节点来判断自己所在的族群。直到某节点的上个节点是自己，那么他是本族群的根节点。
- find 函数，返回大长老。就是通过 father【】数组记录的上层领导，来一层层查找本族群的大长老。（涉及到路径压缩）
- mix 函数，加线。在俩族群A 、B之间连条线，这样两个本不互通的群互通了。随意指定，eg: 指定 A的大长老 a 的pre[ ]不再是自己了，而是B的大长老 b,相当于 加了个 a->b的线。
- 再说路径压缩算法，加快查找的速度。最后生成的树，无法预测，可能是一字长蛇行，这样会查找所属族群的复杂度会大大提高。那么尝试路径压缩算法，尽量使一个族群呈现 两级的树结构，这样查找两步就可以 找到 大长老。
【转自 http://blog.csdn.net/u013546077/article/details/64509038】
前导点（上级领导）的设置：
【这种初始化用了一下感觉不太好，或者说自己写代码不顺手】初始化，可以都设为-1，先前对每个点编了号的，可以默认 小的作为 先导点，一个个去合并，壮大本朋友圈。
{1,2}，{2,3}，{4,5}分别是已知的朋友关系，最后问 一共有多少个朋友圈。【转自 http://blog.csdn.net/xiaobingRSQ/article/details/74371967】
常见的并查集代码 方法（）
找朋友圈的个数，不用上图的方法吧。不通用，还是用最基本的 初始化的root点是其本身的方法。
例题2 朋友圈个数问题 小米的一道面试题：
假如已知有n个人和m对好友关系，如果两个人是直接或者间接有好友关系，则认为他们属于同一个朋友圈。写程序判断里面有多少朋友圈。
例如：
n = 5, m = 3 r = {(1,2), (2, 3), (4, 5)} 1 2 3 是一个朋友圈， 4 5 是一个朋友圈。
所以输出是2
package test;
public class CircleOfFriends {
public static void main(String[] args){
int link[][] = {{1,2},{2,3},{4,5}};
System.out.print(friendnum(5,3,link));
}
public static int friendnum(int n,int m,int[][]link ){
int father[] = new int[n+1];
primaryset(father);
int x =0,y=0;
for(int i = 0;i<m;i++){
x = find(father,link[i][0]);
y = find(father,link[i][1]);
mix(father,x,y);//判断本边的两个father x和y是否是一个族
}
int cnt =0;
for(int i = 0;i< father.length;i++){
if(father[i] == i)
cnt++;
}
return cnt-=1;//把0去掉，这里没有0这位朋友
}
//初始化father[]
public static void primaryset(int[] father){
for(int i = 0;i<father.length;i++){
father[i] = i;
}
}
//
public static int find(int[]father,int x){
int r = x;
while(father[r] != r){ //father[r]>0表示r之前已经有父亲了
r = father[r];//while循环之后找到了 x的root节点 是 r
}
//路径压缩
while(x!=r){
int temp = father[x];
father[x] = r;
x = temp;
}
return r;
}
public static void mix(int[] father,int x,int y){
if(father[x] == father[y] )
return;//在father：x.y之间有间接连接的这时候，去判断是否父节点一样，如果不一样需要加线。
if(x < y){
father[y] = x;
}
else{
father[x] =y;
}
}
}
转载自原文链接, 如需删除请联系管理员。
原文链接：并查集---找朋友圈个数问题，连通度问题，等的有效算法，转载请注明来源！