一、背景
当我们遇到朋友圈问题时：
a与b是朋友，b和c是朋友，那么我们可以将a、b、c看作一个朋友圈...此外，还有d、f、e等人，他们之间也存在着朋友关系或者没有朋友关系。
问：有多少个朋友圈？d、e是否有朋友关系？等等问题，我们都可以用并查集解决。
二、概念及其实现原理
并查集是一种用于解决组团、配对问题的数据结构，它维护的是一堆集合而不是一个集合。
它需要实现的功能有：
-
makeSet(s)：建立一个新的并查集，其中包含 s 个单元素集合。
初始化
-
unionSet(x, y)：把元素 x 和元素 y 所在的集合合并，要求 x 和 y 所在的集合不相交，如果相交则不合并。
合并
但是，这样的结构是不方便使用的，我们可以压缩路径，将子节点直接指向带头节点。（可以在find的过程中处理）
压缩路径
-
find(x)：找到元素 x 所在的集合的代表，该操作也可以用于判断两个元素是否位于同一个集合，只要将它们各自的代表比较一下就可以了。
三、Java实现
class UnionFind {
// 分组个数
int count;
// 数组的第i位表示i的领头结点
int[] parent;
// 初始化
public UnionFind(int n) {
count = n;
parent = new int[n];
for (int i = 0; i < n; i++) {
parent[i] = i;
}
}
// 查找x的领头结点
public int find(int x) {
List<Integer> list = new ArrayList<>();
while (x != parent[x]) {
list.add(x);
parent[x] = parent[parent[x]];
x = parent[x];
}
// 优化路径
for (int item : list) {
parent[item] = x;
}
return x;
}
// 合并分组
public void union(int x, int y) {
int rootX = find(x);
int rootY = find(y);
if (rootX == rootY) {
return;
}
parent[rootY] = rootX;
count--;
}
}
五、相关算法题
问题描述
有 n 个城市，其中一些彼此相连，另一些没有相连。如果城市 a 与城市 b 直接相连，且城市 b 与城市 c 直接相连，那么城市 a 与城市 c 间接相连。
省份 是一组直接或间接相连的城市，组内不含其他没有相连的城市。
给你一个 n x n 的矩阵 isConnected ，其中 isConnected[i][j] = 1 表示第 i 个城市和第 j 个城市直接相连，而 isConnected[i][j] = 0 表示二者不直接相连。
返回矩阵中 省份 的数量。
示例
解题思路
实质是朋友圈问题，直接套用并查集即可。
代码示例（JAVA）
class Solution {
public int findCircleNum(int[][] isConnected) {
int people = isConnected.length;
UnionFind unionFind = new UnionFind(people);
for (int i = 0; i < people; i++) {
for (int j = 0; j < people; j++) {
if (isConnected[i][j] == 1) {
unionFind.union(i, j);
}
}
}
return unionFind.count;
}
class UnionFind {
// 分组个数
int count;
// 数组的第i位表示i的领头结点
int[] parent;
// 初始化
public UnionFind(int n) {
count = n;
parent = new int[n];
for (int i = 0; i < n; i++) {
parent[i] = i;
}
}
// 查找x的领头结点
public int find(int x) {
List<Integer> list = new ArrayList<>();
while (x != parent[x]) {
list.add(x);
parent[x] = parent[parent[x]];
x = parent[x];
}
// 优化路径
for (int item : list) {
parent[item] = x;
}
return x;
}
// 合并分组
public void union(int x, int y) {
int rootX = find(x);
int rootY = find(y);
if (rootX == rootY) {
return;
}
parent[rootY] = rootX;
count--;
}
}
}
问题描述
给你一个由 1（陆地）和 0（水）组成的的二维网格，请你计算网格中岛屿的数量。
岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。
此外，你可以假设该网格的四条边均被水包围。
示例
解题思路
这道题同样可以看作朋友圈问题，假设二维网格的长宽为m、n，那么共有m * n个人；那么朋友关系如何建立？可以通过节点四周的连接情况进行判断。
另外要注意的是，并查集中的count要记录的是陆地的分组数量。
代码示例（JAVA）
class Solution {
static int[][] xys = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
public int numIslands(char[][] grid) {
int m = grid.length;
int n = grid[0].length;
// 建并查集
UnionFind unionFind = new UnionFind(grid);
for (int i = 0; i < grid.length; i++) {
for (int j = 0; j < grid[0].length; j++) {
if (grid[i][j] == '1') {
for (int[] xy : xys) {
// 遍历周围的陆地/水情况，合并分组
if (i + xy[0] >= 0 && i + xy[0] < m && j + xy[1] >= 0 && j + xy[1] < n
&& grid[i + xy[0]][j + xy[1]] == '1') {
unionFind.union(i * n + j, (i + xy[0]) * n + (j + xy[1]));
}
}
}
}
}
return unionFind.count;
}
class UnionFind {
// 分组个数(陆地)
int count;
// 数组的第i位表示i的领头结点
int[] parent;
// 初始化
public UnionFind(char[][] grid) {
count = 0;
int m = grid.length;
int n = grid[0].length;
parent = new int[m * n];
for (int i = 0; i < m * n; i++) {
parent[i] = i;
if (grid[i / n][i % n] == '1') {
count++;
}
}
}
// 查找x的领头结点
public int find(int x) {
List<Integer> list = new ArrayList<>();
while (x != parent[x]) {
list.add(x);
parent[x] = parent[parent[x]];
x = parent[x];
}
// 优化路径
for (int item : list) {
parent[item] = x;
}
return x;
}
// 合并分组
public void union(int x, int y) {
int rootX = find(x);
int rootY = find(y);
if (rootX == rootY) {
return;
}
parent[rootY] = rootX;
count--;
}
}
}
问题描述
给你一个 m x n 的矩阵 board ，由若干字符 X 和 O ，找到所有被 X 围绕的区域，并将这些区域里所有的 O 用 X 填充。
示例
解题思路
找到问题的核心：保留边界的O及与其有连通性的O，其他均为X。
我们依旧可以使用并查集，我们可以建一个虚拟节点，将边界的O及与其有连通性的O与其建立分组关系；最后，遍历矩阵，将和这个虚拟节点没有分组关系的节点，设为X。
代码示例（JAVA）
class Solution {
static int[][] xys = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
public void solve(char[][] board) {
int m = board.length;
int n = board[0].length;
// 建立并查集,多出的节点为虚拟节点
UnionFind unionFind = new UnionFind(m * n + 1);
int virtualNode = m * n;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (board[i][j] == 'O') {
// 周围的'O'直接和虚拟节点合并
if (i == 0 || i == m - 1 || j == 0 || j == n - 1) {
unionFind.union(i * n + j, virtualNode);
} else {
// 中间的'O'和周围的'O'合并
for (int[] xy : xys) {
if (i + xy[0] >= 0 && i + xy[0] < m
&& j + xy[1] >= 0 && j + xy[1] < n
&& board[i + xy[0]][j + xy[1]] == 'O') {
unionFind.union(i * n + j, (i + xy[0]) * n + j + xy[1]);
}
}
}
}
}
}
// 和虚拟节点没有连通性的'O'改为'X'
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (unionFind.find(i * n + j) != unionFind.find(virtualNode)) {
board[i][j] = 'X';
}
}
}
}
class UnionFind {
// 分组个数
int count;
// 数组的第i位表示i的领头结点
int[] parent;
// 初始化
public UnionFind(int n) {
count = n;
parent = new int[n];
for (int i = 0; i < n; i++) {
parent[i] = i;
}
}
// 查找x的领头结点
public int find(int x) {
List<Integer> list = new ArrayList<>();
while (x != parent[x]) {
list.add(x);
parent[x] = parent[parent[x]];
x = parent[x];
}
// 优化路径
for (int item : list) {
parent[item] = x;
}
return x;
}
// 合并分组
public void union(int x, int y) {
int rootX = find(x);
int rootY = find(y);
if (rootX == rootY) {
return;
}
parent[rootY] = rootX;
count--;
}
}
}
网友评论