CS61B： 并查集（不相交集）及其简单实现（一）

1：什么是并查集？

所谓并查集，就是没有共同元素的多个集合。比如有如下几个集合：

A：{1，11，21}；B：{22，45，18}；C：{31，91，81}；D：{22，11，81}
A ∩ B=空集，所以A和B是并查集；
A ∩ C=空集，所以A和C也是并查集；
B ∩ C=空集，所以B和C也是并查集；
A ∩ D={11}，有共同元素11，那A和D就不是并查集，同理B和D，C和D。

2：并查集的应用场景有哪些？

根据1中的定义，其实不难看出，并查集的应用，主要是用来根据某些特征对元素（数据）进行分类和归属判断。
这里的元素，可以是城市个体、可以是家族里的个体、基因里的某个片段、甚至是犯罪团伙中的一个小卡拉米。

举1个例子：

例1：A市出现了频繁的盗窃案件。我作为JC蜀黍通过各种观察，目前确认了10名犯罪嫌疑人。在案件初期，我们并不知道这10名犯罪分子，是一个团伙里的，还是隶属于多个团伙。
于是乎，我办公室的小黑板上，只能先把名字给列上，用编号表示就是:
1，2，3，4，5，6，7，8，9，10

在这个阶段，由于缺乏证据，我只能推断，他们是单兵作战的，于是我可以把他们单独作为一个集合，即：
{1}，{2}，{3} ...... {10}；

随着对案件调查的深入，我以及我的同事们，有了如下惊人发现：

• 嫌犯1和嫌犯2是一伙的；{1，2}
• 嫌犯4和嫌犯7是远房亲戚；{4，7}
• 嫌犯2和嫌犯9以前踩缝纫机的时候，在同一个号子里蹲过，我们此时又可以通过2把9和1联系起来；{1，2，3}
• 嫌犯3和嫌犯10来自同一个镇下的两个村，这两个村相距三公里；{3，10}
• 嫌犯5和嫌犯6，嫌犯8某天一起吃饭；{5，6，8}

以上，我捋清了10个嫌犯的关系，那么现在我们要做的就是根据这些条件确定到底有几个团伙！
由此，我们不同组分别得出了如下的结论：
{1，2，9}，{4，7}，{3，10}，{5，6，8}

继续深入调查，冒出的嫌疑人，越来越多，关系越来越复杂，小黑屋的小黑板，已经完全写不下了，于是我决定用计算机知识，来管理这些嫌疑人的关系。于是又引发出了一个新问题，我TM该怎么管理这些人的关系？ 于是并查集的基操出现了！

3：并查集的基操有哪些？

我在2中，捋清了犯罪分子的关系。如果有的新的犯罪嫌疑人出现在视线中，我该做什么？
比如我在盯1号的同时，嫌疑人11号出现了，我从没见过11号，我要做的就是：

• 和其他组交叉对比，确认11号是否已经记录在案；
• 确认11号所隶属的犯罪团伙；

于是，在此，引出了并查集最主要的操作：

• 判断11号是否已经被其他组记录，很显然没有；【 isConnect(others, 11) 】
• 我盯的是1号，11号和1号出现，很显然是和1号一伙的，那么我要做的就是把1号和11号关联起来；【 connect(1,11) 】

至此，我们引出了并查集的两个方法：void connect(T1,T2) 和 boolean isConnect(T1,T2);

4：让我们用计算机语言构建上述模型！

• 嫌疑犯档案

public class Criminal {  
  
private int number;  
private String name;  
  
private int age;  
  
private String gender;  
  
private String crimeDes;  
  
public int getNumber() {  
return number;  
}  
  
public void setNumber(int number) {  
this.number = number;  
}  
  
public String getName() {  
return name;  
}  
  
public void setName(String name) {  
this.name = name;  
}  
  
public int getAge() {  
return age;  
}  
  
public void setAge(int age) {  
this.age = age;  
}  
  
public String getGender() {  
return gender;  
}  
  
public void setGender(String gender) {  
this.gender = gender;  
}  
  
public String getCrimeDes() {  
return crimeDes;  
}  
  
public void setCrimeDes(String crimeDes) {  
this.crimeDes = crimeDes;  
}

@Override  
public String toString () {  
return "嫌疑人编号: " + this.number + "\t嫌疑人姓名:"+this.name + "\t嫌疑人性别:"+this.gender  
+"\t嫌疑人年龄:" + this.age + "\t嫌疑人涉嫌罪行: "+ this.crimeDes;  
}
}

• 构建模型：开始只确认了10名嫌犯。

public class CriminalDisJointSetCase {  
  
  
private final int[] criminalNumbers;  
private final Set criminalGroupNumbers = new HashSet();
  
public CriminalDisJointSetCase(int discoveredCriminalNumbers) {  
//我们知道，嫌疑人肯定不只discoveredCriminalNumbers个人，所以不妨用大一点的数组来存储嫌疑人的编号；  
criminalNumbers = new int[discoveredCriminalNumbers * 2];  
for (int i = 0; i < discoveredCriminalNumbers; i++) {  
criminalNumbers[i] = i;  
}  
}  

public void connect(int numberOfSuspectA, int numberOfSuspectB) {  
this.criminalNumbers[numberOfSuspectB] = this.criminalNumbers[numberOfSuspectA];  
this.criminalGroupNumbers.add(this.criminalNumbers[numberOfSuspectB]);
}  
  
  
public boolean isConnected(int numberOfSuspectA, int numberOfSuspectB) {  
return this.criminalNumbers[numberOfSuspectA] == this.criminalNumbers[numberOfSuspectB];  
}  
  
public int[] getCriminalNumbers() {  
return this.criminalNumbers;  
}
  
}

• 构建嫌疑人关系网

public class DisJointSetLauncher {  

public static void main(String[] args) {  
Criminal[] criminals = new Criminal[20];  
//一开始只发现了10名嫌疑人

for (int i = 0; i < criminals.length ; i++) {

Criminal criminal = new Criminal();

criminal.setNumber(i);

criminal.setAge(new Random().nextInt(18,40));

criminal.setGender("Male");

criminal.setName("Thief-"+i);

criminal.setCrimeDes("入室盗窃");

criminals[i] = criminal;

}  
//开始为嫌疑人之间建立关系网

CriminalDisJointSetCase criminalDisJointSetCase = new CriminalDisJointSetCase(10);  
//原始关系网

//expected: 0~9，-1 ...... -1

//Arrays.stream(criminalDisJointSetCase.getCriminalNumbers()).boxed().forEach(System.out::print);  
//判断嫌疑人1和2是否是同一个团伙的

//一开始的时候，没有发现，所以这里应该返回false

System.out.println();

System.out.println(criminalDisJointSetCase.isConnected(1,2));  
/**

* 特征1：经过数日侦察，发现嫌疑人1和2一起分赃，于是我们把嫌疑人归并到同一个团伙中去

*/  
criminalDisJointSetCase.connect(criminals[1].getNumber(),criminals[2].getNumber());  
//此时，嫌疑人1和2，他们的数组值，应该是相等的

//即，输出结果应该是：-1，1，1，3，4....9，-1, ...... -1

//由于我们把2的团伙编号，用嫌疑犯1的number替换，所以我们称之为Thief-1团伙

//Arrays.stream(criminalDisJointSetCase.getCriminalNumbers()).boxed().forEach(System.out::print);  
//此时我们再判断1和2是否是一个团伙中的: expect: true

System.out.println();

System.out.println(criminalDisJointSetCase.isConnected(criminals[1].getNumber(),criminals[2].getNumber()));  
/**

* 特征2：经过对比户口，嫌疑犯4和嫌疑犯7是远房亲戚，于是我们把4和7归并到同一个团伙中去

*/

//false

System.out.println(criminalDisJointSetCase.isConnected(criminals[4].getNumber(),criminals[7].getNumber()));

criminalDisJointSetCase.connect(criminals[4].getNumber(),criminals[7].getNumber());

//输出结果应该是：-1，1，1，3，4,5,6,4,8,9，-1, ...... -1

//Arrays.stream(criminalDisJointSetCase.getCriminalNumbers()).boxed().forEach(System.out::print);

//true

System.out.println();

System.out.println(criminalDisJointSetCase.isConnected(criminals[1].getNumber(),criminals[2].getNumber()));  
/**

* 特征3：嫌犯2和嫌犯9以前踩缝纫机的时候，在同一个号子里蹲过，我们此时又可以通过2把9和1联系起来

*/  
//false

System.out.println(criminalDisJointSetCase.isConnected(criminals[1].getNumber(),criminals[9].getNumber()));  
criminalDisJointSetCase.connect(criminals[2].getNumber(),criminals[9].getNumber());

//输出结果应该是：-1，1，1，3，4,5,6,4,8,1......

//Arrays.stream(criminalDisJointSetCase.getCriminalNumbers()).boxed().forEach(System.out::print);

//true

System.out.println();

System.out.println(criminalDisJointSetCase.isConnected(criminals[1].getNumber(),criminals[9].getNumber()));  
/**

* 特征4：嫌犯3和嫌犯10来自同一个镇下的两个村，这两个村相距三公里

*/

System.out.println(criminalDisJointSetCase.isConnected(criminals[3].getNumber(),criminals[10].getNumber()));  
criminalDisJointSetCase.connect(criminals[3].getNumber(),criminals[10].getNumber());

//输出结果应该是：-1，1，1，3，4,5,6,4,8,1，3，-1....

Arrays.stream(criminalDisJointSetCase.getCriminalNumbers()).boxed().forEach(System.out::print);

//true

System.out.println();

System.out.println(criminalDisJointSetCase.isConnected(criminals[3].getNumber(),criminals[10].getNumber()));  
/**

* 特征5：嫌犯5和嫌犯6，嫌犯8某天一起吃饭

*/  
System.out.println(criminalDisJointSetCase.isConnected(criminals[5].getNumber(),criminals[6].getNumber()));  
criminalDisJointSetCase.connect(criminals[5].getNumber(),criminals[6].getNumber());

criminalDisJointSetCase.connect(criminals[6].getNumber(),criminals[8].getNumber());

//输出结果应该是：-1，1，1，3，4,5,5,4,5,1，3，-1....

Arrays.stream(criminalDisJointSetCase.getCriminalNumbers()).boxed().forEach(System.out::print);

//true

System.out.println();

System.out.println(criminalDisJointSetCase.isConnected(criminals[5].getNumber(),criminals[8].getNumber()));  
//此时，团伙编号为：1，3，4，5

System.out.println(criminalDisJointSetCase.discoveredCriminalGroupNumbers());

//对应的团伙成员为：

for (Integer currentNumber : criminalDisJointSetCase.discoveredCriminalGroupNumbers()) {

System.out.println("当前的团伙编号：" + currentNumber);

System.out.println("当前的团伙成员为： ");

for (int i = 1; i