Chiriri's blog
Iekr
2022-04-05
目录

并查集

# 并查集

并查集是树形结构，常常在题目中用来判断两个元素是否属于同一个集合，每个集合都有一个特征性元素称为这个集合的 father，如果两个元素的 father 相同，则说明这两个元素属于同一集合，若这两个元素的 father 不相同，则说明这两个元素不属于一个集合。并查集就是这样一种支持合并和查询的树形数据结构。

  • 初始化 把每个点所在集合初始化为其自身。 通常来说，这个步骤在每次使用该数据结构时只需要执行一次，无论何种实现方式，时间复杂度均为。
  • 查找 查找元素所在的集合，即根节点。
  • 合并 将两个元素所在的集合合并为一个集合。 通常来说，合并之前，应先判断两个元素是否属于同一集合，这可用上面的 “查找” 操作实现。

# 547. 省份数量 (opens new window)

# 递归方法

	public int findCircleNum(int[][] isConnected) {
		int n = isConnected.length;
		UnionFind unionFind = new UnionFind(n);
		for (int i = 0; i < isConnected.length; i++) {
			for (int j = i + 1; j < isConnected[i].length; j++) {
				if (isConnected[i][j] == 1) { // j和i 相互认识
					unionFind.union(i, j);
				}
			}

		}
		return unionFind.sets;
	}

	public static class UnionFind {
		static int sets;
		static int[] arr;

		public UnionFind(int n) {
			this.sets = n;
			this.arr = new int[n];
			for (int i = 0; i < arr.length; i++) {
				arr[i] = i;// 初始化并查集数组 每个节点父元素为自己
			}
		}

		// 找父节点
		public static int find(int a) {
			if (a == arr[a]) {
				return a;
			}
			arr[a] = find(arr[a]);//路径压缩
			return arr[a];
		}

		//合并节点
		public void union(int i, int j) {
            if(find(i) != find(j)){ //如果他们两的父节点 不是一个
			    arr[find(i)] = find(j); //
                sets--;
            }
			
		}

	}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45

# 数组栈实现

	public int findCircleNum(int[][] isConnected) {
		int n = isConnected.length;
		UnionFind unionFind = new UnionFind(n);
		for (int i = 0; i < isConnected.length; i++) {
			for (int j = i + 1; j < isConnected[i].length; j++) {
				if (isConnected[i][j] == 1) {
					unionFind.union(i, j); // 两节点认识 合并节点
				}
			}
		}
		return unionFind.getSets();

	}

	public static class UnionFind {
		// 并查集数组
		private int[] parent;
		// i所在的集合 大小是多少
		private int[] size;
		// 辅助结构 用于实现栈
		private int[] help;
		// 一共有多少个集合
		private int sets;

		public UnionFind(int n) {
			parent = new int[n];
			size = new int[n];
			help = new int[n];
			sets = n;
			// 初始化并查集数组 每个节点的父节点是自身
			for (int i = 0; i < parent.length; i++) {
				parent[i] = i;
				size[i] = 1; // 只有自己一个节点
			}
		}

		// 查找父节点
		public int find(int i) {
			int hi = 0;// 辅助数组下标
			// 找父节点
			while (i != parent[i]) {
				help[hi++] = i;// 记录路径
				i = parent[i];
			}
			// 路径压缩
			for (hi--; hi >= 0; hi--) {
				parent[help[hi]] = i; // 将路径上的节点的父节点 全部标记为最顶的父节点i
			}

			return i; // 返回最顶的父节点

		}

		// 合并节点
		public void union(int i, int j) {
			int f1 = find(i); // 找到这个两节点的父节点
			int f2 = find(j);
			if (f1 != f2) { // 他们两认识 父节点又不相同 进行合并
				if (size[f1] >= size[f2]) { // 将小size的数组 合并到大size的去
					size[f1] += size[f2];
					parent[f2] = f1; // 更新f2的父节点为f1的父节点
				} else {
					size[f2] += size[f1];
					parent[f1] = f2;
				}
				sets--;
			}
		}

		public int getSets() {
			return sets;
		}

		public void setSets(int sets) {
			this.sets = sets;
		}

	}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78

# 200. 岛屿数量 (opens new window)

感染问题，经典写法使用 dfs 搜索，但可以改为并查集实现。

# 深搜写法

	public int numIslands(char[][] grid) {
		int ans = 0;
		for (int i = 0; i < grid.length; i++) {
			for (int j = 0; j < grid[i].length; j++) {
				if (grid[i][j] == '1') {
					ans++;
					dfs(grid, i, j);
				}
			}
		}
		return ans;
	}

	private void dfs(char[][] grid, int i, int j) {
		if (i < 0 || i == grid.length || j < 0 || j == grid[i].length || grid[i][j] != '1') {
			// 越界 或 当前岛屿不是1(陆地)
			return;
		}
		grid[i][j] = 3; //感染更改标记
		dfs(grid, i + 1, j);
		dfs(grid, i - 1, j);
		dfs(grid, i, j + 1);
		dfs(grid, i, j - 1);

	}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

# 包装成类存储写法

由于 0,0 是没有数据，我们先遍历第 0 行和第 0 列的岛屿（优化时间），再遍历其他岛屿，每个岛屿只搜索上方和左方岛屿。

这里我们将岛屿为 1 的位置存储为我们的自定义类，存储的为内存地址防止多个岛屿值相同情况，

	public static int numIslands1(char[][] board) {
		int row = board.length;
		int col = board[0].length;
		Dot[][] dots = new Dot[row][col];
		List<Dot> dotList = new ArrayList<>();
		for (int i = 0; i < row; i++) {
			for (int j = 0; j < col; j++) {
				if (board[i][j] == '1') {
					dots[i][j] = new Dot();
					dotList.add(dots[i][j]);
				}
			}
		}
		UnionFind1<Dot> uf = new UnionFind1<>(dotList);
		for (int j = 1; j < col; j++) {
			// (0,j)  (0,0)跳过了  (0,1) (0,2) (0,3)
			if (board[0][j - 1] == '1' && board[0][j] == '1') {
				uf.union(dots[0][j - 1], dots[0][j]);
			}
		}
		for (int i = 1; i < row; i++) {
			if (board[i - 1][0] == '1' && board[i][0] == '1') {
				uf.union(dots[i - 1][0], dots[i][0]);
			}
		}
		for (int i = 1; i < row; i++) {
			for (int j = 1; j < col; j++) {
				if (board[i][j] == '1') {
					if (board[i][j - 1] == '1') {
						uf.union(dots[i][j - 1], dots[i][j]);
					}
					if (board[i - 1][j] == '1') {
						uf.union(dots[i - 1][j], dots[i][j]);
					}
				}
			}
		}
		return uf.sets();
	}

	public static class Dot {

	}

	public static class Node<V> {

		V value;

		public Node(V v) {
			value = v;
		}

	}

	public static class UnionFind1<V> {
		public HashMap<V, Node<V>> nodes;
		public HashMap<Node<V>, Node<V>> parents;
		public HashMap<Node<V>, Integer> sizeMap;

		public UnionFind1(List<V> values) {
			nodes = new HashMap<>();
			parents = new HashMap<>();
			sizeMap = new HashMap<>();
			for (V cur : values) {
				Node<V> node = new Node<>(cur);
				nodes.put(cur, node);
				parents.put(node, node);
				sizeMap.put(node, 1);
			}
		}

		public Node<V> findFather(Node<V> cur) {
			Stack<Node<V>> path = new Stack<>();
			while (cur != parents.get(cur)) {
				path.push(cur);
				cur = parents.get(cur);
			}
			while (!path.isEmpty()) {
				parents.put(path.pop(), cur);
			}
			return cur;
		}

		public void union(V a, V b) {
			Node<V> aHead = findFather(nodes.get(a));
			Node<V> bHead = findFather(nodes.get(b));
			if (aHead != bHead) {
				int aSetSize = sizeMap.get(aHead);
				int bSetSize = sizeMap.get(bHead);
				Node<V> big = aSetSize >= bSetSize ? aHead : bHead;
				Node<V> small = big == aHead ? bHead : aHead;
				parents.put(small, big);
				sizeMap.put(big, aSetSize + bSetSize);
				sizeMap.remove(small);
			}
		}

		public int sets() {
			return sizeMap.size();
		}

	}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102

# 将二维数组转为一维写法

二维转一维：i * 列数 + j

	public int numIslands(char[][] grid) {
		int row = grid.length; // 行
		int col = grid[0].length; // 列
		UnionFind uf = new UnionFind(grid);
		for (int i = 1; i < col; i++) {
			if (grid[0][i - 1] == '1' && grid[0][i] == '1') {
				uf.union(0, i - 1, 0, i);
			}
		}
		for (int i = 1; i < row; i++) {
			if (grid[i - 1][0] == '1' && grid[i][0] == '1') {
				uf.union( i - 1, 0, i,0);
			}
		}

		for (int i = 1; i < row; i++) {
			for (int j = 1; j < col; j++) {
				if (grid[i][j] == '1') {
					if (grid[i][j - 1] == '1') {
						uf.union(i, j - 1, i, j);
					}
					if (grid[i - 1][j] == '1') {
						uf.union(i - 1, j, i, j);
					}
				}
			}
		}

		return uf.getSets();

	}

	public static class UnionFind {
		int[] parent; // 并查集数组
		int[] size; // 存储为大小
		int[] help; // 压缩路径辅助数组 用于模拟栈
		int col; // 列
		int sets; // 父节点数量

		// 初始化
		public UnionFind(char[][] grid) {
			col = grid[0].length; // 列
			sets = 0;
			int row = grid.length; // 行
			int len = row * col;// 陆地和水的总数量
			parent = new int[len];
			size = new int[len];
			help = new int[len];

			for (int i = 0; i < row; i++) {
				for (int j = 0; j < col; j++) {
					if (grid[i][j] == '1') {
						int ind = index(i, j);
						parent[ind] = ind;
						size[ind] = 1;
						sets++;
					}
				}
			}

		}

		private int index(int i, int j) {
			// 二维转一维：i*列数+j
			return i * col + j;
		}

		private int find(int i) {
			int hi = 0;
			// 找父节点
			while (i != parent[i]) {
				help[hi++] = i;
				i = parent[i];
			}
			// 压缩路径
			for (hi--; hi >= 0; hi--) {
				parent[help[hi]] = i;
			}

			return i;
		}

		private void union(int r1, int c1, int r2, int c2) {
			int a = index(r1, c1);
			int b = index(r2, c2);
			int f1 = find(a);
			int f2 = find(b);
			if (f1 != f2) {
				if (size[f1] >= size[f2]) {
					size[f1] += size[f2];
					parent[f2] = f1;
				} else {
					size[f2] += size[f1];
					parent[f1] = f2;
				}
				sets--; // 减少父节点数量
			}
		}

		public int getSets() {
			return sets;
		}

		public void setSets(int sets) {
			this.sets = sets;
		}

	}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108

# 305. 岛屿数据 II (opens new window)

m 行和列的 2d 网格图 n 最初充满水。我们可以执行 addLand 操作，将位置 (row, col) 的水变成陆地。给定要操作的位置列表，计算每次 * addLand * 操作后的岛数。岛屿四面环水，由相邻陆地水平或垂直连接而成。您可以假设网格的所有四个边缘都被水包围。

例子：

输入： m = 3，n = 3，位置 = [[0,0]，[0,1]，[1,2]，[2,1]]
输出： [1,1,2,3]
1
2

解释：

最初，二维网格 grid 充满水。（假设 0 代表水，1 代表土地）。

0 0 0
0 0 0
0 0 0
1
2
3

操作 #1：addLand (0, 0) 将 grid [0][0] 处的水变成陆地。

1 0 0
0 0 0 岛屿数 = 1
0 0 0
1
2
3

操作 #2：addLand (0, 1) 将 grid [0][1] 处的水变成陆地。

1 1 0
0 0 0 岛屿数 = 1
0 0 0
1
2
3

操作 #3：addLand (1, 2) 将 grid [1][2] 处的水变成陆地。

1 1 0
0 0 1 岛屿数 = 2
0 0 0
1
2
3

操作 #4：addLand (2, 1) 将 grid [2][1] 处的水变成陆地。

1 1 0
0 0 1 岛屿数 = 3
0 1 0
1
2
3
public static List<Integer> numIslands21(int m, int n, int[][] positions) {
		UnionFind unionFind = new UnionFind(m, n);
		List<Integer> ans = new ArrayList<>();
		for (int[] i : positions) {
			ans.add(unionFind.connect(i[0], i[1]));
		}

		return ans;

	}

	public static class UnionFind {
		int[] parent;
		int[] help;
		int[] size;
		final int row;
		final int col;
		int sets;

		public UnionFind(int row, int col) {
			this.row = row;
			this.col = col;
			int len = row * col;
			parent = new int[len];
			help = new int[len];
			size = new int[len];
			sets = 0;
		}

		public int index(int r, int c) {
			return r * col + c;
		}

		public int find(int i) {
			int hi = 0;
			while (i != parent[i]) {
				help[hi++] = i;
				i = parent[i];
			}
			for (hi--; hi >= 0; hi--) {
				parent[help[hi]] = i;
			}
			return i;
		}

		public void union(int r1, int c1, int r2, int c2) {
			if (r1 < 0 || r1 == row || c1 < 0 || c1 == col || r2 < 0 || r2 == row || c2 < 0 || c2 == col) {
				// 边界处理
				return;
			}
			int a = index(r1, c1);
			int b = index(r2, c2);
			if (size[a] == 0 || size[b] == 0) {
				// 两节点 有任意一节点未经过 合并无意义
				return;
			}
			int f1 = find(a);
			int f2 = find(b);
			if (f1 != f2) {
				if (size[f1] >= size[f2]) {
					size[f1] += size[f2];
					parent[f2] = f1;
				} else {
					size[f2] += size[f1];
					parent[f1] = f2;
				}
				sets--;
			}

		}

		public int connect(int r, int c) {
			int index = index(r, c);
			// 该节点之前没有经过的
			if (size[index] == 0) {
				// 初始化
				parent[index] = index;
				size[index] = 1;
				sets++;
				// 上下左右合并
				union(r + 1, c, r, c);
				union(r - 1, c, r, c);
				union(r, c + 1, r, c);
				union(r, c - 1, r, c);
			}
			return sets;
		}

	}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
编辑 (opens new window)
上次更新: 2023/12/06, 01:31:48
贪心
图

← 图→

最近更新
01
k8s
06-06
02
进程与线程
03-04
03
计算机操作系统概述
02-26
更多文章>
Theme by Vdoing | Copyright © 2022-2025 Iekr | Blog