1. 定义

在计算机科学中，并查集（英文：Disjoint-set data structure，直译为不交集数据结构）是一种数据结构，用于处理一些不交集（Disjoint sets，一系列没有重复元素的集合）的合并及查询问题。并查集支持如下操作：
查询:查询某个元素属于哪个集合，通常是返回集合内的一个“代表元素”。这个操作是为了判断两个元素是否在同一个集合之中。
合并：将两个集合合并为一个。
添加：添加一个新集合，其中有一个新元素。添加操作不如查询和合并操作重要，常常被忽略。
由于支持查询和合并这两种操作，并查集在英文中也被称为联合-查找数据结构（Union-find data structure）或者合并-查找集合（Merge-find set）。

2.并查集

• 可用于解决“图的动态连通性”问题；
• 在解决某些问题时，可通过设置合适的“虚拟顶点”将元素进行分类，也就是同一类的元素互相连通，如此可将所有元素分为不同的连通域，继而进行其他操作；
• 并查集底层使用一维数组存储多个“森林”，但实际只考虑某顶点的祖先顶点，将祖先顶点作为该顶点的直接父节点；
• 底层一维数组的下标对应每个顶点的编号，其中存储该顶点的祖先顶点；
• 初始情况下，顶点的直接父顶点为顶点本身；
• 并查集代码涉及三个部分：1）初始化：构建父节点数组；2）查询操作：查询某顶点的父顶点；3）合并操作：将两棵不同子树合并为一棵，其中一个根节点作为合并后树的根节点；
• 如果两个顶点连通，则他们的直接父节点是一样的；

3.模板代码

package com.northsmile.union;/*** @author NorthSmile* @version 1.0* @date 2023/4/19&21:46* 并查集模板代码*/
public class Template {// 存储编号为i的顶点的祖先顶点编号public int[] parent;// 记录连通分量的数量public int count;/*** 初始化*/public Template(int n){// 初始化节点数量为n，节点编号依次为0~n-1parent=new int[n+1];for (int i=1;i<=n;i++){// 初始状态：自己做自己的父节点parent[i]=i;}count=n;}/*** 查询某节点的祖先节点* @param v* @return*/public int find(int v){// 说明此时该节点独立if (parent[v]==v){return v;} else {// 无路径压缩
//            return find(parent[v]);// 路径压缩parent[v]=find(parent[v]);return parent[v];}}/*** 合并顶点v、w* @param v* @param w*/public void union(int v,int w){// 分别确定两顶点的祖先顶点int vP=find(v);int wP=find(w);if (vP==wP){return;}count--;// 以wP作为vp的父顶点，此时v的祖先顶点更新为wP，也就是将v、w为根节点的树合并为一棵树parent[vP]=wP;}/*** 判断v、w之间是否连通* 如果二者连通，他们的祖先顶点一定相同* @param v* @param w* @return*/public boolean connected(int v,int w){// 分别确定两顶点的祖先顶点int vP=find(v);int wP=find(w);return vP==wP;}/*** 返回连通域的数量* @return*/public int count(){return count;}
}

4. 力扣例题

4.1 剑指 Offer II 118. 多余的边

剑指 Offer II 118. 多余的边

树可以看成是一个连通且 无环 的 无向 图。给定往一棵 n 个节点 (节点值 1～n) 的树中添加一条边后的图。添加的边的两个顶点包含在 1到 n 中间，且这条附加的边不属于树中已存在的边。图的信息记录于长度为 n 的二维数组 edges ，edges[i] = [ai, bi]表示图中在 ai 和 bi 之间存在一条边。 请找出一条可以删去的边，删除后可使得剩余部分是一个有着 n个节点的树。如果有多个答案，则返回数组 edges 中最后出现的边。

解题思路：

• 树中任意两个节点之间是连通的；
• n个节点的树中共有n-1条边；
• edges数组长度为n说明最多有一个边是多余的；
• 构成一条边的两个节点如果已经连通，说明二者直接父节点一样，如果此时再对这两个节点进行合并，说明这条边即是多余的；

class Solution {/**** @param edges* @return*/public int[] findRedundantConnection(int[][] edges) {int n=edges.length;UFData uf = new UFData(n);for (int i=0; i<n;i++){if (uf.find(edges[i][0])!=uf.find(edges[i][1])) {uf.union(edges[i][0], edges[i][1]);}else {return edges[i];}}return new int[0];}
}class UFData{public int[] parent;public UFData(int n){parent=new int[n+1];for (int i=1;i<=n;i++){parent[i]=i;}}public int find(int v){if (v==parent[v]){return v;}else{parent[v]=find(parent[v]);return parent[v];}}public void union(int v,int w){int vP=find(v);int wP=find(w);if (vP==wP){return;}parent[vP]=wP;}public boolean connected(int v,int w){return find(v)==find(w);}
}

4.2 力扣695. 岛屿的最大面积

695. 岛屿的最大面积

给你一个大小为 m x n 的二进制矩阵 grid 。岛屿 是由一些相邻的 1 (代表土地) 构成的组合，这里的「相邻」要求两个 1 必须在
水平或者竖直的四个方向上 相邻。你可以假设 grid 的四个边缘都被 0（代表水）包围着。岛屿的面积是岛上值为 1
的单元格的数目。计算并返回 grid 中最大的岛屿面积。如果没有岛屿，则返回面积为 0 。

class Solution {public int maxAreaOfIsland(int[][] grid) {int m=grid.length;int n=grid[0].length;UFData uf = new UFData(m * n);int[][] directions=new int[][]{{-1,0},{1,0},{0,-1},{0,1}};  // 上下左右boolean haveUnion=false;boolean haveOne=false;for (int i=0;i<m;i++){for (int j=0;j<n;j++){if (grid[i][j]==1){haveOne=true;// 连接邻域for (int k=0;k<4;k++){int cR=i+directions[k][0];int cC=j+directions[k][1];if (cR<0||cR>=m||cC<0||cC>=n){continue;}if(grid[cR][cC]==1){haveUnion=true;uf.union(i*n+j,cR*n+cC);}}}}}
//        System.out.println(Arrays.toString(uf.size));return haveOne?haveUnion?uf.maxArea:1:0;}private static class UFData{public int[] parent;public int[] size;public int maxArea;public UFData(int n){parent=new int[n];size=new int[n];Arrays.fill(size,1);for (int i=0;i<n;i++){parent[i]=i;}}public int find(int v){if (v==parent[v]){return v;}else{parent[v]=find(parent[v]);return parent[v];}}public void union(int v,int w){int vP=find(v);int wP=find(w);if (vP==wP){return;}parent[vP]=wP;size[wP]+=size[vP];maxArea=Math.max(maxArea,size[wP]);}public boolean connected(int v,int w){return find(v)==find(w);}}
}

参考资料：

• 麦克老师讲算法
• labuladong算法小抄
• 维基百科