所谓并查集，是指支持集合的合并和查询操作的数据结构。
- 合并：将两个集合合并为一个。
- 查询：查询某个元素属于哪个集合，通常是返回集合内的一个代表元素（例如二叉树的所有结点可视为属于同一个集合，代表元素为根结点）。查询操作是为了判断两个元素是否在同一个集合之中。
但是一般来说，并查集特指其中最常见的一种实现：不交集森林。不交集森林把 每一个集合以一棵树表示，每一个结点即是一个元素，结点保存着到它父结点的引用，数的根结点保存一个指向自身的引用。
添加操作
添加操作 MakeSet(x) 添加一个元素 x，这个元素自身就是一棵树，所以将它标记为根结点。
void MakeSet(x) {
x.parent = x;
}
查询操作
查询操作 Find(x) 从结点 x 开始，找到它所属树的根结点。
TreeNode Find(x) {
if (x.parent == x) return x;
else return Find(x.parent);
}
- 路径压缩优化
在树很不平衡时，上述查询操作可能花费 O(n) 的时间。常见优化是：在向上查询时，把路径上的每个结点都直接连接到根结点上，这样以后查询时就能直接找到根结点。
TreeNode Find(x) {
if(x.parent == x) return x;
x.parent = Find(x.parent);
return x.parent;
}
合并操作
合并操作 Union(x,y) 把两个指定元素所在集合合并为一个。首先找出两个结点对应的两个根结点：
- 如果这两个根结点是同一个，则说明这两个元素本来已经在同一个集合中；
- 否则，使其中一个根结点成为另一个根结点的父结点。
void Union(x, y) {
xRoot = Find(x);
yRoot = Find(y);
if(xRoot != yRoot)
xRoot.parent = yRoot;
}
- 按秩合并优化
上面的合并操作可能会使树变得很不平衡，增加树的深度。为了 控制树的深度，在合并时，比较两棵树的大小，让较小的树合并到较大的树上。
秩（rank） 这个指标常用来衡量树的大小，秩的定义如下：
- 只有一个结点的树，秩为 0。
- 两棵树合并时：
- 如果两棵树的秩相同，合并后树的秩为原来的秩加一。
- 如果两棵树的秩不同，合并后树的秩为原来较大的秩。
在合并时考虑两棵树秩的大小，让较大者成为根结点，这称为按秩合并。
void MakeSet(TreeNode x) {
x.parent = x;
x.rank = 0;
}
void Union(TreeNode x, TreeNode y) {
TreeNode xRoot = Find(x);
TreeNode yRoot = Find(y);
TreeNode large = null, small = null;
if(xRoot != yRoot) {
if(xRoot.rank < yRoot.rank) {
large = yRoot;
small = xRoot;
} else {
large = xRoot;
small = yRoot;
}
small.parent = large; // 设置 parent
if(large.rank == small.rank) // 设置 rank
large.rank += 1;
}
}
200 岛屿数量
给你一个由 '1'（陆地）和 '0'（水）组成的的二维网格，请你计算网格中岛屿的数量。
岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。
此外，你可以假设该网格的四条边均被水包围。
方法一：DFS
遍历每一个网格：
- 如果当前位置为陆地（
grid[i][j]=='1'），则从该位置开始进行 DFS，将搜索过程中遇到的陆地全部标记为'2'。搜索完毕后将结果加一。 - 如果当前位置不是陆地（
grid[i][j]!='1'），则跳过。
int numOfIslands(char[][] grid) {
int rows = grid.length, cols = grid[0].length;
int result = 0;
for(int i = 0; i < rows; i++) {
for(int j = 0; j < cols; j++) {
if(grid[i][j] == '1') {
dfs(grid, i, j);
result++;
}
}
}
return result;
}
void dfs(char[][] grid, int r, int c) {
// base case：下标越界、当前位置为海水或已访问过
if(r < 0 || r >= grid.length || c < 0
|| c >= grid[0].length || grid[r][c] != '1')
return;
// 执行任务：将当前陆地标记为 '2'
grid[r][c] = '2';
// 访问相邻位置
dfs(grid, r-1, c);
dfs(grid, r+1, c);
dfs(grid, r, c-1);
dfs(grid, r, c+1);
}
方法二：BFS
同 DFS 的整体思路一样，也是遍历每一个网格，找到一块陆地就将其放入队列，然后开始 BFS：
- 首先将结果加一；
- 然后将队列中的元素依次出队，检查相邻的四个位置：
- 如果当前位置下标越界或者是海水，或者已访问过，则跳过；
- 如果是陆地则放入队列，并将其修改为
'2'。
- 搜索结束返回结果。
int numOfIslands(char[][] grid) {
int rows = grid.length, cols = grid[0].length;
int result = 0;
// 遍历每一个位置，每遇到一块陆地就开始 BFS
for(int i = 0; i < rows; i++) {
for(int j = 0; j < cols; j++) {
// 遇到陆地开始 BFS
if(grid[i][j] == '1') {
result++;
Queue<int[]> queue = new LinkedList<>();
queue.offer(new int[]{i, j});
grid[i][j] = '2'; // 标记为已访问过
// 开始 BFS
while(!queue.isEmpty()) {
int[] cell = queue.poll();
int x = cell[0], y = cell[1];
int[] dx = {-1, 1, 0, 0};
int[] dy = {0, 0, -1, 1};
for(int k = 0; k < 4; k++) {
int newX = x + dx[k];
int newY = y + dy[k];
// 下标越界
if(newX < 0 || newY == rows || newY < 0 || newY == cols)
continue;
// 已访问过或者是海水
if(grid[newX][newY] != '1')
continue;
// 遇到陆地，则加入队列继续搜索
queue.offer(new int[]{newX, newY});
grid[newX][newY] = '2';
} // for k
} // while(!queue.isEmpty())
} // if(grid[i][j] == '1')
} // for j
} // for i
return result;
}
方法三：并查集
扫描每一个网格，如果当前位置是陆地，则 将它与相邻四个位置的陆地在并查集中进行合并。最终岛屿数量就是 并查集中连通分量的数目。
先定义并查集的类，在其中定义构造函数、查询、合并等操作。
class UnionFind {
int count; // 集合数目，初始时每块陆地自成一个集合
int[] parent;
int[] rank; // 每个集合(树)的秩
// 根据 grid 构造并查集
public UnionFind(char[][] grid) {
count = 0;
int rows = grid.length, cols = grid[0].length;
parent = new int[rows * cols];
rank = new int[rows * cols];
// 遍历每个网格
for(int i = 0; i < rows; i++) {
for(int j = 0; j < cols; j++) {
// 每一块陆地作为一个结点
if(grid[i][j] == '1') {
parent[i * cols + j] = i * cols + j;
count++;
}
rank[i * cols + j] = 0;
}
}
}
public int find(int i) {
if(i != parent[i])
parent[i] = find(parent[i]);
return parent[i];
}
public void union(int x, int y) {
int xRoot = find(x);
int yRoot = find(y);
// 按秩合并优化
if(xRoot != yRoot) {
if(rank[xRoot] > rank[yRoot])
parent[yRoot] = xRoot;
else if(rank[xRoot] < rank[yRoot])
parent[xRoot] = yRoot;
else {
parent[yRoot] = xRoot;
rank[xRoot] += 1;
}
// 合并后数量减一
count--;
}
}
public int getCount() {
return count;
}
}
然后利用并查集统计连通分量数目。
int numOfIslands(char[][] grid) {
int rows = grid.length, cols = grid[0].length;
int result = 0;
// 构造并查集对象
UnionFind uf = new UnionFind(grid);
// 遍历整个 grid
for(int i = 0; i < rows; i++) {
for(int j = 0; j < cols; j++) {
// 发现陆地，则将该陆地与相邻陆地合并
if(grid[i][j] == '1') {
grid[i][j] = '0';
int[] dx = {-1, 1, 0, 0};
int[] dy = {0, 0, -1, 1};
// 查看相邻区块是否为陆地，是则合并
for(int k = 0; k < 4; k++) {
int newX = i + dx[k];
int newY = j + dy[k];
// 当前位置下标越界或不为陆地
if(newX < 0 || newX >= rows || newY < 0
|| newY >= cols || grid[newX][newY] != '1')
continue;
// 将该相邻位置与当期位置对应的集合合并
uf.union(i * cols + j, newX * cols + newY);
} // for k
} // for if
} // for j
} // for i
return uf.getCount();
}
547 省份数量
有 n 个城市，其中一些彼此相连，另一些没有相连。如果城市 a 与城市 b 直接相连，且城市 b 与城市 c 直接相连，那么城市 a 与城市 c 间接相连。
省份 是一组直接或间接相连的城市，组内不含其他没有相连的城市。
给你一个 n x n 的矩阵 isConnected ，其中 isConnected[i][j] = 1 表示第 i 个城市和第 j 个城市直接相连，而 isConnected[i][j] = 0 表示二者不直接相连。
返回矩阵中 省份 的数量。
本题实际上是求图中的连通分量数。
方法一：DFS
遍历所有城市，对于每个城市：
- 如果该城市尚未被访问过，则从该城市开始 DFS：
- 通过矩阵
isConnected得到与该城市直接相连的城市有哪些，这些城市与当前城市同属一个连通分量； - 然后对这些城市继续 DFS，直到同一个连通分量的所有城市都被访问到，即可得到一个省份。
- 通过矩阵
- 遍历完所有城市后，即可得到连通分量总数。
int numOfIsProvinces(int[][] isConnected) {
int cityNum = isConnected.length;
boolean[] visited = new boolean[cityNum];
int result = 0;
for(int i = 0; i < cityNum; i++) {
if(!visited[i]) {
visited[i] = true;
// 从当前城市开始找到一个连通分量
dfs(isConnected, visited, i);
result++;
}
}
return result;
}
void dfs(int[][] isConnected, boolean[] visited, int city) {
// 遍历每个城市
for(int i = 0; i < isConnected.length; i++) {
// 找到相邻城市，从它开始继续搜索
if(isConnected[city][i] == 1 && !visited[i]){
visited[i] = true;
dfs(isConnected, visited, i);
}
}
}
方法二：BFS
和 DFS 的整体思路一样，也是遍历每个城市，从当前城市搜索出整个连通分量，在搜索过程中将遇到的相连的城市标记为已访问。不同之处在于搜索这个连通分量的方式。
int numOfProvinces(int[][] isConnected) {
int cityNum = isConnected.length;
boolean[] visited = new boolean[cityNum];
Queue<Integer> queue = new LinkedList<>();
// 遍历每一个城市，搜索一个连通分量
int result = 0;
for(int i = 0; i < cityNum; i++) {
if(!visited[i]) {
queue.offer(i);
while(!queue.isEmpty()) {
int curCity = queue.poll();
visited[curCity] = true; // 出队后标记为已访问
// 让相邻城市入队，继续下一轮搜索
for(int j = 0; j < cityNum; j++) {
if(isConnected[curCity][j] == 1 && !visited[j]) {
queue.offer(j);
}
}
} // while
result++;
}
}
return result;
}
方法三：并查集
计算连通分量数的另一个方法是使用并查集：
- 初始时，每个城市都自成一个连通分量。
- 遍历每个城市与其他每个城市的连接关系（
isConnected矩阵），如果连个城市之间直接相连，则它们属于同一个连通分量，对它们进行合并。 - 遍历整个矩阵之后，计算 连通分量数，即为省份总数。
int[] parent; // 并查集
int numOfProvinces(int[][] isConnected) {
int cityNum = isConnected.length;
// 初始化并查集
parent = new int[cityNum];
for (int i = 0; i < cityNum; i++) {
parent[i] = i;
}
// 遍历每个城市，相连城市进行合并
for (int i = 0; i < cityNum; i++) {
for (int j = i + 1; j < cityNum; j++) {
if (isConnected[i][j] == 1)
// 每次合并都会让连通分量数减一
union(i, j);
}
}
// 统计连通分量数
int result = 0;
for (int i = 0; i < cityNum; i++)
// 根结点数量 == 连通分量数
if (parent[i] == i) result++;
return result;
}
int find(int index) {
if (parent[index] != index) parent[index] = find(parent[index]);
return parent[index];
}
void union(int x, int y) {
parent[find(x)] = find(y);
}
·
684 冗余连接
给定往一棵 n 个节点 (节点值 1～n) 的树中添加一条边后的图。添加的边的两个顶点包含在 1 到 n 中间，且这条附加的边不属于树中已存在的边。图的信息记录于长度为 n 的二维数组 edges ，edges[i] = [ai, bi] 表示图中在 ai 和 bi 之间存在一条边。
请找出一条可以删去的边，删除后可使得剩余部分是一个有着 n 个节点的树。如果有多个答案，则返回数组 edges 中最后出现的边。
方法：并查集
树是一个连通且无环的无向图，在树中加入一条新边就会出现环，这条边就是本题需要寻找的边。
可以通过并查集寻找这条边。初始时，每个结点都属于不同的连通分量。遍历每条边，判断这条边连接的两个顶点是否属于相同的连通分量。
- 如果属于不同的连通分量，说明在遍历到这条边之前，这两个结点是不连通的，进一步说明不是这条边导致了环的出现。合并这两个顶点分属的连通分量。
- 如果属于相同的连通分量，说明在遍历到这条边之前，这两个结点已经连通，进一步说明这条边是导致环出现的那条边。
int[] parent;
int[] findRedundantConnection(int[][] edges) {
int n = edges.length;
parent = new int[n + 1];
// 构建无交集森林
for (int i = 1; i <= n; i++) {
parent[i] = i;
}
// 遍历每条边
for (int i = 0; i < n; i++) {
int[] edge = edges[i];
int node1 = edge[0], node2 = edge[1];
// 属于不同的连通分量
if (find(node1) != find(node2)) union(node1, node2);
else // 属于相同的连通分量，则当前边就是造成环的边
return edge;
}
return new int[0];
}
// 并查集——查询操作，返回根结点
int find(int index) {
// 路径压缩优化
if (parent[index] != index) parent[index] = find(parent[index]);
return parent[index];
}
// 并查集——合并操作，将 index1 的根结点设置为 index2 的根结点
void union(int index1, int index2) {
parent[find(index1)] = find(index2);
}
399 除法求值
给你一个变量对数组 equations 和一个实数值数组 values作为已知条件，其中 equations[i] = [Ai, Bi] 和 values[i] 共同表示等式 Ai / Bi = values[i] 。每个 Ai 或 Bi 是一个表示单个变量的字符串。
另有一些以数组 queries 表示的问题，其中 queries[j] = [Cj, Dj] 表示第 j 个问题，请你根据已知条件找出 Cj / Dj = ? 的结果作为答案。
返回 所有问题的答案 。如果存在某个无法确定的答案，则用 -1.0 替代这个答案。如果问题中出现了给定的已知条件中没有出现的字符串，也需要用 -1.0 替代这个答案。
方法一：并查集
构建有向图
题目给出的 equations 和 values 可以表示成一个图，equations 中出现的变量就是图的结点，分子分母的关系可以表示成一个有向关系，values 对应的值就是有向边的权值。
路径压缩
在查询一个结点的根结点时，将路径上的所有点的父结点都设为这个根结点，这就是路径压缩。路径压缩可以将一个集合中的所有结点的值都转换成根结点的倍数，从而可以计算出比值。在路径压缩中需要不断更新边上的权值（因为压缩后结点直接指向了根结点，有向边发生变动），过程如下：
class Solution {
// 并查集内部类
private class UnionFind {
private int[] parent;
private double[] weight;
public UnionFind(int n) {
this.parent = new int[n];
this.weight = new double[n];
for(int i = 0; i < n; i++) {
parent[i] = i;
weight[i] = 1.0d;
}
}
public void union(int x, int y, double value) {
int rootX = find(x);
int rootY = find(y);
if(rootX == rootY)
return;
parent[rootX] = rootY;
// 推导关系见下图
weight[rootX] = weight[y] * value / weight[x];
}
public int find(int x) {
if(x != parent[x]) {
int temp_parent = parent[x];
parent[x] = find(temp_parent);
weight[x] *= weight[temp_parent];
}
return parent[x];
}
public double isConnected(int x, int y) {
int rootX = find(x);
int rootY = find(y);
if(rootX == rootY)
return weight[x] / weight[y];
else
return -1.0d;
}
}
double[] calcEquation(List<List<String>> equations, double[] values,
List<List<String>> queries) {
int n = equations.size();
UnionFind uf = new UnionFind(2 * n);
// 第一步：预处理，将变量的值与 id 进行映射，使得并查集的底层使用数组实现，方便编码
Map<String, Integer> hashMap = new HashMap<>();
int id = 0;
for(int i = 0; i < n; i++) {
List<String> equation = equations.get(i);
String var1 = equation.get(0);
String var2 = equation.get(1);
if(!hashMap.containsKey(var1)) {
hashMap.put(var1, id);
id++;
}
if(!hashMap.containsKey(var2)) {
hashMap.put(var2, id);
id++;
}
uf.union(hashMap.get(var1), hashMap.get(var2), values[i]);
}
// 第二步：做查询
int m = queries.size();
double[] result = new double[m];
for(int i = 0; i < m; i++) {
String var1 = queries.get(i).get(0);
String var2 = queries.get(i).get(1);
Integer id1 = hashMap.get(var1);
Integer id2 = hashMap.get(var2);
if(id1 == null || id2 == null)
result[i] = -1.0d;
else
result[i] = uf.isConnected(id1, id2);
}
return result;
}
}
方法二：BFS
用同样的方式建图，然后对于每个查询，就可以从起点出发，通过 BFS 不断更新起点与当前点之间的路径长度，直到搜索到终点为止。
class Pair {
int index;
double value;
Pair(int index, double value) {
this.index = index;
this.value = value;
}
}
class Solution {
double calcEquation(List<List<String>> equations, double[] values,
List<List<String>> queries) {
int id = 0;
// 将字符串映射为 id
Map<String, Integer> map = new HashMap<>();
int n = equations.size();
for(int i = 0; i < n; i++) {
String node1 = equations.get(i).get(0);
String node2 = equations.get(i).get(1);
if(!map.containsKey(node1))
map.put(node1, id++);
if(!map.containsKey(node2))
map.put(node2, id++);
}
// 建图：用 List<Pair> 类型的数组来存储每个点相连的所有点及其比值
List<Pair>[] edges = new List[id];
for(int i = 0; i < id; i++)
edges[i] = new ArrayList<Pair>();
for(int i = 0; i < n; i++) {
String node1 = equations.get(i).get(0);
String node2 = equations.get(i).get(1);
Integer id1 = map.get(node1);
Integer id2 = map.get(node2);
edges[id1].add(new Pair(id2, values[i]));
edges[id2].add(new Pair(id1, 1.0/values[i]));
}
// BFS，为每个查询求得答案
int m = queries.size();
double[] result = new double[m];
for(int i = 0; i < m; i++) {
String node1 = queries.get(i).get(0);
String node2 = queries.get(i).get(1);
double ans = -1.0;
if(map.containsKey(node1) && map.containsKey(node2)) {
int id1 = map.get(node1);
int id2 = map.get(node2);
if(id1 == id2) {
ans = 1.0;
} else {
Queue<Integer> queue = new LinkedList<>();
queue.offer(id1); // 从第一个点开始搜索
double[] ratios = new double[id];
Arrays.fill(ratios, -1.0);
ratios[id1] = 1.0;
while(!queue.isEmpty() && ratios[id2] < 0) {
int x = queue.poll();
// 访问相邻结点，直到搜索到 id2
for(Pair pair : edges[x]) {
int y = pair.index;
double val = pair.value;
if(ratios[y] < 0) {
rratios[y] = ratios[x] * val;
queue.offer(y);
}
}
}
ans = ratios[id2]; // 找到一个答案
}
}
result[i] = ans;
}
return result;
}
}