并查集基础
并查集是一个用于解决 disjoint sets 类问题的常用数据结构，用于处理集合中
元素的归属 find O(1)
集合的融合 union O(1)
Online algorithm, stream of input
计算 number of connected components
不支持 delete
- Find
HashMap<Integer, Integer> map = new HashMap<>(
public int find(int i) {
int parent = map.get(i);
while (parent != map.get(parent)) {
parent = map.get(parent);
}
return parent;
}
这里面实际上就是通过一个map去找一个node的源头。
- Union
public void union(int x, int y) {
int parentx = find(x);
int parenty = find(y);
if (parentx != parenty) {
map.put(parentx, parenty);
}
}
可以说只跟源头有关系。
323. Number of Connected Components in an Undirected Graph
首先每一个初始node的父亲节点是自己。用hashmap来做，写好初始化，union和find的方法，然后用一个set统计一下总共有多少个不同的连通块就可以了，只要把union-find的模板掌握熟练即可。
这道题和丧尸群那道题感觉很相似，关键点就在于在input中给出了n，作为节点总数，这个很重要，这就说明了一点，在最特殊的case中，最多只能有n个连通块，不可能超过n。因为union-find是需要节点总数用来初始化的，就像那道丧尸群标记的题一样。而number of islands中，我们不知道总共的岛屿群数量上限，所以很难用union-find来做。
public class Solution {
class UnionFind{
Map<Integer, Integer> map;
public UnionFind(int n) {
map = new HashMap<>();
for (int i = 0; i < n; i++) {
map.put(i, i);
}
}
public int find(int x) {
int parent = map.get(x);
while (parent != map.get(parent)) {
parent = map.get(parent);
}
return parent;
}
public void union(int x, int y) {
int parentx = find(x);
int parenty = find(y);
if (parentx != parenty) {
map.put(parentx, parenty);
}
}
}
public int countComponents(int n, int[][] edges) {
if (edges == null || edges.length == 0) return n;
UnionFind uf = new UnionFind(n);
for (int i = 0; i < edges.length; ++i) {
int node1 = edges[i][0];
int node2 = edges[i][1];
uf.union(node1, node2);
}
Set<Integer> set = new HashSet<>();
for (int i = 0; i < n; ++i) {
set.add(uf.find(i));
}
return set.size();
}
}
200. Number of Islans
二维转一维的经典题。
public class Solution {
class UnionFind{
public int count;
public int[] parent;
public UnionFind(char[][] grid) {
int m = grid.length;
int n = grid[0].length;
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
if (grid[i][j] == '1') {
count++;
}
}
}
parent = new int[m * n];
for (int i = 0; i < m * n; ++i) {
parent[i] = i;
}
}
public int find(int p) {
while (p != parent[p]) {
parent[p] = parent[parent[p]];
p = parent[p];
}
return p;
}
public void union(int p, int q) {
int rootP = find(p);
int rootQ = find(q);
if (rootP == rootQ) return;
parent[rootP] = rootQ;
count--;
}
}
public int numIslands(char[][] grid) {
if (grid == null || grid.length == 0 || grid[0].length == 0) return 0;
UnionFind uf = new UnionFind(grid);
int m = grid.length;
int n = grid[0].length;
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
if (grid[i][j] == '0') continue;
int p = i * n + j;
int q;
if (i > 0 && grid[i - 1][j] == '1') {
q = p - n;
uf.union(p, q);
}
if (i < m - 1 && grid[i + 1][j] == '1') {
q = p + n;
uf.union(p, q);
}
if (j > 0 && grid[i][j - 1] == '1') {
q = p - 1;
uf.union(p, q);
}
if (j < n - 1 && grid[i][j + 1] == '1') {
q = p + 1;
uf.union(p, q);
}
}
}
return uf.count;
}
}