public class UnionFind1 {
private int[] parent;
private int[] high;
public UnionFind1(int size) {
high = new int[size];
parent = new int[size];
for (int i = 0; i < size; i++) {
high[i] = 1;
parent[i] = i;
}
}
public boolean isConnected(int firstElement, int secondElement) {
return find(firstElement) == find(secondElement);
}
public int find(int element) {
while (element != parent[element]) {
// 要找element最终的老大哥,不等,则不断更新
element = parent[element];
}
return element;
}
public void UnionElements(int firstElement, int secondElement) {
int firstRoot = find(firstElement);
int secondRoot = find(secondElement);
if (firstRoot == secondRoot)
return;
if (high[firstRoot] > high[secondRoot])
parent[secondRoot] = firstRoot;
else if (high[firstRoot] < high[secondRoot])
parent[firstRoot] = secondRoot;
else {
parent[secondRoot] = firstRoot;
high[firstRoot] += 1;
}
}
}
基于重量(孩子节点个数)优化的并查集
public class UnionFind2 {
private int[] parent;
private int[] weight;
public UnionFind2(int size) {
this.parent = new int[size];
this.weight = new int[size];
for (int i = 0; i < size; i++) {
this.parent[i] = i;
this.weight[i] = 1;
}
}
public int find(int element) {
while (element != parent[element]) {
// 当前结点指向自己父亲的父亲,减少深度
parent[element] = parent[parent[element]];
element = parent[element];
}
return element;
}
public boolean isConnected(int firstElement, int secondElement) {
return find(firstElement) == find(secondElement);
}
public void unionElements(int firstElement, int secondElement) {
int firstRoot = find(firstElement);
int secondRoot = find(secondElement);
// 如果已经属于同一个集合了,就不用再合并了。
if (firstRoot == secondRoot) {
return;
}
if (weight[firstRoot] > weight[secondRoot]) {
parent[secondRoot] = firstRoot;
weight[firstRoot] += weight[secondRoot];
} else {// weight[firstRoot] <= weight[secondRoot]
parent[firstRoot] = secondRoot;
weight[secondRoot] += weight[firstRoot];
}
}
}
并查集的应用
畅通工程
某省调查城镇交通状况,得到现有城镇道路统计表,表中列出了每条道路直接连通的城镇。省政府“畅通工程”的目标是使全省任何两个城镇间都可以实现交通(但不一定有直接的道路相连,只要互相间接通过道路可达即可)。问最少还需要建设多少条道路?
思路: 在并查集中进行合并操作,求出最后剩下多少个组(集合)。这些组之间是互相不可达的。假如有M个组,那其实再需要M-1条连线就可以把他们连接起来了。所以组数 - 1 就是最后答案。(原先每个元素自成一组,每执行一次合并操作,组数减一)
public UnionFind(int size) {
parent = new int[size];
weight = new int[size];
this.group = size;
for (int i = 0; i < size; i++) {
parent[i] = i;
weight[i] = 1;
}
}
public void UnionElement(int firstElement, int secondElement) {
int firstRoot = find(firstElement);
int secondRoot = find(secondElement);
if (firstRoot == secondRoot)
return;
if (weight[firstRoot] > weight[secondRoot]) { // 谁的孩子多谁就是新的根节点
parent[secondRoot] = firstRoot;
weight[firstRoot] += weight[secondRoot];
} else {
parent[firstRoot] = secondRoot;
weight[secondRoot] += weight[firstRoot];
}
this.group--; // 每进行一次合并操作,集合个数减一
}
岛屿数量
给你一个由 ‘1’(陆地)和 ‘0’(水)组成的的二维网格,请你计算网格中岛屿的数量。岛屿总是被水包围,并且每座岛屿只能由水平方向或竖直方向上相邻的陆地连接形成。此外,你可以假设该网格的四条边均被水包围。链接:https://leetcode-cn.com/problems/number-of-islands
题目大致意思是: 在二维矩阵中,搜索一共有多少个连通域('1’表示可达,即连通,此处是4连通域)
思路: 属于一个连通域,即所含元素均属于同一个集合。采用并查集,统计网格中‘1’的个数,当做初始集合个数,‘1’对应的存储下标即为各自初始根节点。当前若遍历到‘1’则与它的4连通域元素进行合并操作,每进行一次合并,集合总数减一。最后连通域的个数即为集合的个数。
public NumOfLands(char[][] grid) {
this.group = 0;
int row = grid.length;
int col = grid[0].length;
this.parent = new int[row * col];
this.weight = new int[row * col];
for (int i = 0; i < row; i++) {
for (int j = 0; j < col; j++) {
if (grid[i][j] == '1') {
parent[i * col + j] = i * col + j; // 1 对应的存储下标值当做其根节点
group++;
weight[i * col + j] = 1;
}
}
}
}
public int numIslands(char[][] grid) {
if (grid == null || grid.length == 0)
return 0;
int R = grid.length, C = grid[0].length;
for (int i = 0; i < R; i++) {
for (int j = 0; j < C; j++) {
if (grid[i][j] == '1') {
grid[i][j] = '0';
if (i - 1 >= 0 && grid[i - 1][j] == '1') {
unionElements(i * C + j, (i - 1) * C + j);
}
if (i + 1 < R && grid[i + 1][j] == '1') {
unionElements(i * C + j, (i + 1) * C + j);
}
if (j - 1 >= 0 && grid[i][j - 1] == '1') {
unionElements(i * C + j, i * C + j - 1);
}
if (j + 1 < C && grid[i][j + 1] == '1') {
unionElements(i * C + j, i * C + j + 1);
}
}
}
}
return getGroup();
}
最短的桥
在给定的二维二进制数组 A 中,存在两座岛。(岛是由四面相连的 1 形成的一个最大组。)现在,我们可以将 0 变为 1,以使两座岛连接起来,变成一座岛。返回必须翻转的 0 的最小数目。(可以保证答案至少是 1 。)链接:https://leetcode-cn.com/problems/shortest-bridge
题目大意: 就是网格中有两个由’1’构成的连通域,让找到使两个连通域成为一个连通域的最少操作数是多少(即将0变1的最少次数)
public class 最短的桥 {
public static int shortestBridge(int[][] A) {
int R = A.length, C = A[0].length;
int[][] colors = dfs(A);
Queue queue = new LinkedList();
Set target = new HashSet();
for (int r = 0; r < R; r++) {
for (int c = 0; c < C; c++) {
if (colors[r][c] == 1)
queue.offer(new Node(r, c, 0));
else if (colors[r][c] == 2)
target.add(r * C + c); // 目标点坐标(目标点不止一个)
}
}
while (!queue.isEmpty()) {
Node node = queue.poll();
if (target.contains(node.r * C + node.c))
return node.depth - 1;
for (int k : neighbors(A, node.r, node.c)) {
int nr = k / C, nc = k % C;
if (colors[nr][nc] != 1) {
queue.add(new Node(nr, nc, node.depth + 1));
colors[nr][nc] = 1; // 切记要将访问过的标记成不可再访问
}
}
}
return 0;
}
public static int[][] dfs(int[][] A) { // 使用栈进行模拟
int R = A.length, C = A[0].length;
int[][] colors = new int[R][C];
int t = 0; // 为每个连通域打上一个标记
for (int r = 0; r < R; r++) {
for (int c = 0; c < C; c++) {
if (colors[r][c] == 0 && A[r][c] == 1) {
Deque stack = new ArrayDeque();
stack.push(r * C + c);
colors[r][c] = ++t;
while (!stack.isEmpty()) {
int id = stack.pop();
int row = id / C, col = id % C;
for (int k : neighbors(A, row, col)) {
int nr = k / C, nc = k % C;
if (A[nr][nc] == 1 && colors[nr][nc] == 0) {
colors[nr][nc] = t;
stack.push(nr * C + nc);
}
}
}
}
}
}
return colors;
}
public static List neighbors(int[][] A, int r, int c) {
int R = A.length, C = A[0].length;
List ans = new ArrayList();
if (0 <= r - 1)
ans.add((r - 1) * R + c);
if (0 <= c - 1)
ans.add(r * R + (c - 1));
if (r + 1 < R)
ans.add((r + 1) * R + c);
if (c + 1 < C)
ans.add(r * R + (c + 1));
return ans;
}
}
class Node {
int r, c, depth;
public Node(int r, int c, int depth) {
this.r = r;
this.c = c;
this.depth = depth;
}
}



