1. 数据结构
主要包括：
- 并查集中的元素
- 元素的父节点
- 并查集中的代表元素（可以理解为根节点）
- 并查集的元素数量（主要用在2个并查集合并时）
/**
* 并查集中元素的数据结构
*
* @param <V>
*/
public static class Element<V>{
public V value;
public Element(V value) {
this.value = value;
}
}
/**
* 并查集的数据结构
*
* @param <V>
*/
public static class UnionFindSet<V>{
/**
* key: 业务实体
* value: 被并查集包装的 元素
*/
public Map<V, Element<V>> elementMap;
/**
* key: 并查集中的元素
* value: 元素的父元素，代表元素的父是自己
*/
public Map<Element<V>, Element<V>> fatherMap;
/**
* key: 并查集的代表元素
* value：代表元素下，包含的并查集中元素的数量
*/
public Map<Element<V>, Integer> sizeMap;
2. 相关操作
2.1 初始化
通常会将业务元素加入到并查集中，默认：
- 每个元素各自为一个并查集（在find的过程中才去合并）
- 并查集的代表元素就是自己
- 并查集的数量为1
public UnionFindSet(List<V> list){
//初始化
elementMap = new HashMap<>();
fatherMap = new HashMap<>();
sizeMap = new HashMap<>();
for (V value : list) {
Element<V> element = new Element<>(value);
elementMap.put(value, element);
//默认并查集元素的代表元素为自己，各自为一个并查集，所以size=1
fatherMap.put(element, element);
sizeMap.put(element, 1);
}
}
2.2 查找代表元素
为了防止并查集的链过长导致性能退化，需要在合并过程中进行打扁平，可以理解为将一个只有一条路径的树打成了一个多叉树
- 给定element，一直往上找代表元素
- 将沿途的元素的父元素都设置为代表元素，即打平优化操作
/**
* 根据并查集中的某个元素查找该并查集的代表元素
*
* @param element
* @return
*/
public Element<V> findHead(Element<V> element){
Stack<Element<V>> path = new Stack<>();
//1.给定element，一直往上找代表元素（代表元素的特征是自己的父是自己）
while (element != fatherMap.get(element)){
path.push(element);
element = fatherMap.get(element);
}
//2.将沿途的元素的父元素都设置为代表元素，打扁平，减少查询时间，防止链过长导致性能退化
while (!path.isEmpty()){
fatherMap.put(path.pop(), element);
}
return element;
}
2.3 判断是否为同一个并查集
前提是2个查询的元素，必须是在并查集中（即被初始化过）
/**
* 给定2个业务实体，判断他们是否在一个并查集中
* @param a
* @param b
* @return
*/
public boolean isSameSet(V a,V b){
if(elementMap.containsKey(a) && elementMap.containsKey(b)){
//判断各自的代表元素是否相同，如果相同，那么证明在一个并查集中
return findHead(elementMap.get(a)).equals(findHead(elementMap.get(b)));
}
return false;
}
2.4 合并
步骤：
- 前提：合并的元素必须经过初始化
- 查询合并元素的各自的代表元素
- 如果代表元素相同，证明已经是一个并查集了无需合并
- 如果代表元素不相同，那么将小的并查集挂在大的下面，即[数量少的代表元素]的代表元素设置为[数量多的代表元素]
/**
* 合并操作
* @param a
* @param b
*/
public void union(V a, V b){
//1.只处理并查集中的元素
if(elementMap.containsKey(a) && elementMap.containsKey(b)){
Element<V> af = findHead(elementMap.get(a));
Element<V> bf = findHead(elementMap.get(b));
//2.如果a的代表元素和b的代表元素不是一个，才进行合并
if(!af.equals(bf)){
Element<V> big = sizeMap.get(af) >= sizeMap.get(bf) ? af : bf;
Element<V> small = af.equals(big) ? bf : af;
//3.小的挂在大的下，即[数量少的代表元素]的代表元素设置为[数量多的代表元素]
fatherMap.put(small, big);
sizeMap.put(big, sizeMap.get(big) + sizeMap.get(small));
sizeMap.remove(small);
}
}
}
3. 时间复杂度
查询和合并的时间复杂度为：O(log* n),即 log start，是一个迭代对数
O(log* n) 是比O(log n) 还要快，近似等于O(1)，比O(1)慢一点点
4. 实战题目
4.1 省份数量
题目描述：
有 n 个城市，其中一些彼此相连，另一些没有相连。如果城市 a 与城市 b 直接相连，且城市 b 与城市 c 直接相连，那么城市 a 与城市 c 间接相连。
给你一个 n x n 的矩阵 isConnected ，其中 isConnected[i][j] = 1 表示第 i 个城市和第 j 个城市直接相连，而 isConnected[i][j] = 0 表示二者不直接相连。
返回矩阵中 省份 的数量。
思路：
- 将城市的序号初始化到并查集中
- isConnected[i][j] = 1，代表i这个城市和j这个城市是连通的，合并加入并查集
- 返回最后并查集中代表元素的数量，就是省份的数量
public int findCircleNum(int[][] isConnected) {
if(isConnected == null || isConnected[0] == null){
return 0;
}
return infectProcess(isConnected);
}
public int unionFindSetProcess(int[][] isConnected){
int row = isConnected.length;
int column = isConnected[0].length;
//1. 构建并查集
int maxLength = Math.max(row, column);
List<Integer> list = new ArrayList<>();
for (int i = 0; i < maxLength; i++) {
list.add(i);
}
UnionFind.UnionFindSet<Integer> unionFindSet = new UnionFind.UnionFindSet<>(list);
//2. 合并
for (int x = 0; x < column; x++) {
for (int y = 0; y < row; y++) {
//如果为1标识，x和y是可以合并一个并查集
if(isConnected[x][y] == 1){
unionFindSet.union(x, y);
}
}
}
//3. 返回
return unionFindSet.sizeMap.size();
}
4.2 多余的边（冗余链接）
题目描述：
给定往一棵 n 个节点 (节点值 1～n) 的树中添加一条边后的图。添加的边的两个顶点包含在 1 到 n 中间，且这条附加的边不属于树中已存在的边。图的信息记录于长度为 n 的二维数组 edges ，edges[i] = [ai, bi] 表示图中在 ai 和 bi 之间存在一条边。
请找出一条可以删去的边，删除后可使得剩余部分是一个有着 n 个节点的树。如果有多个答案，则返回数组 edges 中最后出现的边。
思路：
- 将一个连接上的2个节点，全部初始化到并查集
- 遍历，如果2个节点不在一个并查集中，那么合并为一个并查集
- 如果2个节点已经在一个并查集中，判断为冗余的边
- 根据题目要求，如果有多个答案，则返回数组 edges 中最后出现的边
public int[] findRedundantConnection(int[][] edges) {
if(edges == null || edges.length == 0 || edges[0].length!=2){
return null;
}
return unionFindSetProcess(edges);
}
public int[] unionFindSetProcess(int[][] edges){
int[] result = new int[2];
//1.构建并查集
int row = edges.length;
int column = edges[0].length;
Set<Integer> list = new HashSet<>();
for (int i = 0; i < row; i++) {
list.add(edges[i][0]);
list.add(edges[i][1]);
}
UnionFind.UnionFindSet<Integer> unionFindSet = new UnionFind.UnionFindSet<>(new ArrayList<>(list));
//2.合并
for (int i = 0; i < row; i++) {
boolean sameSet = unionFindSet.isSameSet(edges[i][0], edges[i][1]);
if(!sameSet){
//2个元素不在一个并查集中，那么合并为一个并查集
unionFindSet.union(edges[i][0],edges[i][1]);
}else{
//2个元素已经在一个并查集中，判断为冗余的边, 根据题目要求，如果有多个答案，则返回数组 edges 中最后出现的边
result[0] = edges[i][0];
result[1] = edges[i][1];
}
}
//3.返回
return result;
}
4.3 最长连续序列
题目描述：
给定一个未排序的整数数组 nums ，找出数字连续的最长序列（不要求序列元素在原数组中连续）的长度。
请你设计并实现时间复杂度为 O(n) 的算法解决此问题。
思路：
- 将数组中的元素初始化到并查集，同时在一个map中记录下
- 遍历，如果num-1在map中，那么将num 和 num-1合并
- 返回并查集中代表元素集合最大的，就是最长连续序列的长度
public int longestConsecutive(int[] nums) {
if(nums ==null || nums.length == 0){
return 0;
}
return unionFindSetProcess(nums);
}
public int unionFindSetProcess(int[] nums){
//1. 构建加入并查集
List<Integer> list = new ArrayList<>();
Map<Integer, Integer> map = new HashMap<>();
for (int num : nums) {
list.add(num);
map.put(num, 1);
}
UnionFind.UnionFindSet<Integer> unionFindSet = new UnionFind.UnionFindSet<>(list);
//2. 合并
for (int num : nums) {
//如果num-1在map中，那么将num 和 num-1合并
if(map.containsKey(num - 1)){
unionFindSet.union(num - 1, num);
}
}
//3. 返回代表元素集合最大的
return unionFindSet.sizeMap.values().stream().sorted(Comparator.reverseOrder()).collect(Collectors.toList()).get(0);
}
4.4 情侣牵手
题目描述：
n 对情侣坐在连续排列的 2n 个座位上，想要牵到对方的手。
人和座位由一个整数数组 row 表示，其中 row[i] 是坐在第 i 个座位上的人的 ID。情侣们按顺序编号，第一对是 (0, 1)，第二对是 (2, 3)，以此类推，最后一对是 (2n-2, 2n-1)。
返回 最少交换座位的次数，以便每对情侣可以并肩坐在一起。 每次交换可选择任意两人，让他们站起来交换座位。
思路：
- 构建并查集，将情侣对编号初始化到并查集
- 2个2个遍历，找出不在一起的[情侣对编号]，合并在一起，代表后续这2对情侣要换位置，如果有交换有依赖关系就加入一个并查集
- 统计并查集中各个代表元素的size-1，就是总合并交换次数
public int minSwapsCouples(int[] row) {
if(row == null || row.length == 0 || row.length % 2 == 1){
return -1;
}
return unionFindSetProcess(row);
}
public int unionFindSetProcess(int[] row){
//1.构建并查集，将情侣对编号初始化到并查集
int length = row.length;
int couplesSize = length/2;
List<Integer> list = new ArrayList<>();
for (int i = 0; i < couplesSize; i++) {
list.add(i);
}
UnionFind.UnionFindSet<Integer> unionFindSet = new UnionFind.UnionFindSet<>(list);
//2.2个2个遍历，找出不在一起的[情侣对编号]，合并在一起，代表后续这2对情侣要换位置，如果有交换有依赖关系就加入一个并查集
for (int i = 0; i < length; i +=2) {
int firstCouplesNo = row[i]/2;
int secondCouplesNo = row[i+1]/2;
//不在一起
if(firstCouplesNo != secondCouplesNo){
unionFindSet.union(firstCouplesNo, secondCouplesNo);
}
}
//3.统计，并查各个代表元素的size，合并交换次数并返回
int swaps = 0;
for (Map.Entry<UnionFind.Element<Integer>, Integer> entry : unionFindSet.sizeMap.entrySet()) {
//size-1
Integer size = entry.getValue();
swaps += size-1;
}
return swaps;
}
4.5 封闭岛屿的数目
题目描述：
二维矩阵 grid 由 0 （土地）和 1 （水）组成。岛是由最大的4个方向连通的 0 组成的群，封闭岛是一个 完全 由1包围（左、上、右、下）的岛。
请返回 封闭岛屿 的数目。
思路：
- 构建并查集，将岛（0）的加入并查集
- 遍历，如果岛连通，那么合并到并查集，根据遍历顺序，看下边和右边即可
- 重新遍历，判断岛的位置，如果不是封闭的的岛，淘汰
- 返回封闭岛屿的数目
public int closedIsland(int[][] grid) {
if(grid== null || grid.length == 0 || grid[0] ==null || grid[0].length==0){
return 0;
}
return unionFindSetProcess(grid);
}
public int unionFindSetProcess(int[][] grid){
//1. 构建并查集，将岛（0）的加入并查集
int row = grid.length;
int column = grid[0].length;
List<Integer> list = new ArrayList<>();
for (int i = 0; i < row; i++) {
for (int j = 0; j < column; j++) {
if(grid[i][j] == 0){
//格子的编号
list.add(i * column + j);
}
}
}
UnionFind.UnionFindSet<Integer> unionFindSet = new UnionFind.UnionFindSet<>(list);
//2. 遍历，如果岛连通，那么合并到并查集
for (int i = 0; i < row; i++) {
for (int j = 0; j < column; j++) {
if(grid[i][j] == 0){
//右边为岛，合并
if(j+1< column && grid[i][j+1] == 0){
//按编号合并
unionFindSet.union(i * column + j, i * column + (j + 1));
}
//下边为岛，合并
if(i+1<row && grid[i+1][j] == 0){
//按编号合并
unionFindSet.union(i * column + j, (i+1) * column + j);
}
}
}
}
//3. 重新遍历，判断岛的位置，并淘汰
Set<UnionFind.Element> headValueList = new HashSet<>();
for (int i = 0; i < row; i++) {
for (int j = 0; j < column; j++) {
if(grid[i][j] == 0){
//边界位置
if(i == 0 || i == row-1 || j == 0 || j == column-1){
//查找并查集的代表元素，先记录，后淘汰
UnionFind.Element<Integer> headElement = unionFindSet.findHead(unionFindSet.elementMap.get(i * column + j));
headValueList.add(headElement);
}
}
}
}
//淘汰并返回结果
int size = unionFindSet.sizeMap.size();
for (UnionFind.Element element : headValueList) {
//如果不是封闭的的岛，淘汰
if(unionFindSet.sizeMap.containsKey(element)){
size--;
}
}
return size;
}
