并查集（union-find算法）：一种树型结构，用于处理一些不交集的合并及查询问题
最重要的两个方法：
find：用于查找元素属于哪一个子集，可以用来判断两个元素是否属于同一个集合
union：将两个子集合并成为一个集合
趣味理解：其实并查集的运用就是一个小弟确认帮派、找老大的操作。例如在古惑仔中，洪兴和东星都有自己的龙头大哥，而且洪兴和东星是死对头，双方遇见了就会干架，但是洪兴和东星都规定帮内成员不能打架，而且帮派等级森严，小弟们只知道自己的大哥是谁，而不知道龙头大哥是谁，这时双方都不能确认对方是不是死对头，这时候他们就打电话确认对方的身份。
例如
场景一：A和B在烧烤摊因为一串热狗准备干架了，但是苦于规矩，他们要先打电话确认对方的身份。
这时A打电话给自己的老大山鸡，山鸡打电话给老大陈浩南，陈浩南又打电话给蒋先生；B也给自己的大哥大飞打电话，大飞又打电话给蒋先生，然后A报了自己的身份说我是蒋先生的人，此时B也说我也是蒋先生的人。A和B看了看对方都笑了，原来是兄弟，所以他们就和好了，两个人一起吃了这串热狗。
场景二：B又在烧烤摊和C发生矛盾了，这次是因为一串韭菜，他们这时就打电话确认对方的身份
B打电话给大哥大飞，大飞打电话给蒋先生，同时C也给自己的老大乌鸦打电话，乌鸦又给大哥骆驼打电话。B说我是蒋先生的人，C说我是骆驼的人，双方一听，马上叫上自己的兄弟，TMD是敌人，往死里整，然后B就赢到了这串韭菜，东星输给了洪兴。古惑仔的世界胜者为王，败者为寇，此时东星已经被洪兴打败了，所以东星被洪兴吞并了。
东星被吞并后
具体实现步骤
init：定义一个集合（古惑仔的世界），有N个元素（N个古惑仔），每个元素都是一个集合（每个人都是自己的龙头大哥），所以此时有N个集合（N个帮派）
-
public
static
int[] teenage=
null;
//元素集合
-
public
static
int count =
0;
//集合数量
-
-
//初始化
-
public static void init(int N){
-
count = N;
-
heroes =
new
int[N];
-
for (
int i =
0; i < N; i++){
-
heroes[i] = i;
-
}
-
}
find：元素确定自己所在集合（小弟找龙头大哥的操作）
-
public static int find(int id){
-
// 如果自己不是龙头大哥就继续寻找
-
while (id != teenage[id]){
-
id = teenage[id];
-
}
-
return id;
-
}
union：将两个子集合并成为一个集合（两个帮派合并）
-
public static void union(int p, int q){
-
int pID = find(p);
// 确定自己所在集合（找龙头大哥）
-
int qID = find(q);
// 确定自己所在集合（找龙头大哥）
-
if (pID == qID){
-
// 同一个帮派，不能干架，吃烧烤去
-
return;
-
}
-
// 不是同一个帮派，召集人干架，但是由于q要比p要厉害一点，所以呢，q就吞并了p
-
// p的龙头大哥就成了q的龙头大哥的小弟
-
teenage[pID] = qID;
-
// 集合减少一个（p的帮派消失了）
-
count--;
-
}
完整代码
-
package com.company.unionFind;
-
-
import java.util.Scanner;
-
-
public
class UF_quickUnion {
-
-
public
static
int[] teenage =
null;
-
public
static
int count =
0;
-
-
public static void init(int N){
-
count = N;
-
teenage =
new
int[N];
-
for (
int i =
0; i < N; i++){
-
teenage[i] = i;
-
}
-
}
-
public static int find(int id){
-
while (id != teenage[id]){
-
id = teenage[id];
-
}
-
return id;
-
}
-
-
public static void union(int p, int q){
-
int pID = find(p);
-
int qID = find(q);
-
if (pID == qID){
-
return;
-
}
-
teenage[pID] = qID;
-
count--;
-
}
-
-
public static void main(String[] args){
-
init(
10);
-
Scanner scanner =
new Scanner(System.in);
-
int p, q;
-
while((p = scanner.nextInt()) != -
1 && (q = scanner.nextInt()) != -
1){
-
union(p,q);
-
}
-
-
System.out.println(
"剩下 " + count +
" 个集合");
-
}
-
}
测试数据
-
4 3
-
3 8
-
6 5
-
9 4
-
2 1
-
8 9
-
5 0
-
7 2
-
6 1
-
1 0
-
6 7
输出
剩下 2 个集合
转载：https://blog.csdn.net/weixin_41856902/article/details/104930763