《经典算法》并查集
题目：
某国家有N个小岛组成，经过多年的基础设施累积，若该岛屿之间建立若干桥梁，先重新完善该国的行政区划，规定只要有桥梁连接的岛屿则归属于同一个城市（可以通过其他岛屿中转），问该国可以划分为多少个城市？
思路：
初始化完毕之后，对该动态连通图有几种可能的操作：
- 查询节点属于的组
数组对应位置的值即为组号
- 判断两个节点是否属于同一个组
分别得到两个节点的组号，然后判断组号是否相等
- 连接两个节点，使之属于同一个组
分别得到两个节点的组号，组号相同时操作结束，不同时，将其中的一个节点的组号换成另一个节点的组号
- 获取组的数目
初始化为节点的数目，然后每次成功连接两个节点之后，递减1
源码：
package com.wyj.quickfind;
import java.util.Scanner;
/**
*
* @author wyj《经典算法》~并查集
* 某国家有N个小岛组成，经过多年的基础设施累积，若该岛屿之间建立若干桥梁，先重新完善该国的行政区划，规定只要有桥梁连接的岛屿则归属于同一个城市（可以通过其他岛屿中转），问该国可以划分为多少个城市？
*
* 法一：给每一个小岛分组，有连接的属于用一个组，否则不属于同一个组；
* 法二：给每一个小岛分组，有连接两岛[m,n] 记A[m]=m,A[n]=m即m是树根，n是m的叶节点；
*
*/
public class quickFind {
static private int n;
static private int[] A;
public static void main(String[] args) {
// TODO Auto-generated method stub
Scanner sc = new Scanner(System.in);
System.out.print("请输入小岛个数 n:");
n = sc.nextInt();
A = new int[n];
initFun();
System.out.println("请输入岛A岛B表示A-B两岛有桥梁 ");
while(true) {
System.out.print("请输入岛A，输入-1结束输出");
int p = sc.nextInt();
if(p==-1) {
break;
}
System.out.print("请输入岛B，输入-1结束输出");
int q = sc.nextInt();
if(q==-1) {
break;
}
union_Zu(p,q);
}
System.out.println("该国共有"+getN()+"个城市");
}
static private int getN() {
return n;
}
static private void initFun() {
for(int i=0;i<n;i++) {//初始化每个到属于不同组
A[i] = i;
}
}
//法一
static private int find_Zu(int i) {
return A[i];//返回的是组编号
}
static private void union_Zu(int p,int q) {
int p_value = find_Zu(p);
int q_value = find_Zu(q);
if(p_value==q_value) {
return ;
}else {
for(int i=0;i<A.length;i++) {
if(A[i]==q_value) {//把所有组值为q_value变成组织是p_value(牵一发而动全身)
A[i] = p_value;
}
}
n--;//计算当前组数
}
}
//法二
static private int find_Tree(int i) {
while(A[i]!=i) {
i = A[i];
}
return i;//返回的是父节点
}
static private void union_Tree(int p,int q) {
int p_value = find_Tree(p);
int q_value = find_Tree(q);
if(p_value==q_value) {
return ;
}else {
A[q] = p;
n--;
}
}
}