并查集简介
并查集：一开始，把a，b，c放入并查集，a自己一个集合，b自己一个，c自己一个
提供的方法 1.boolean isSameSet(a,b)，判断ab是否在同一个集合
2.void union(a,b),把a所在集合的全部，和b所在集合的全部，两个大集合合并
怎么实现的方法一
对于每个元素，都有一个指针指向自己
查询a，b是否在同一个集合，对于a，a往上到不能再往上的节点就是他的代表节点，也就是a
b同理，代表节点不同，所以ab所在的集合不同
我们把一个节点往上找，找到不能再往上的那个节点叫集合的代表节点
那如何实现union合并呢
并查集有自己的机制，记录每一个集合大小是多少
然后union（a，e）时，把b的指针直接挂到a后面，union（a，c）时，小的挂到大的上，c挂到a后面
如果再union（b,d）然后union(d,e)怎么union，先顺着d往上找找到b，然后顺着e往上找找到a，小的挂大的，只需改代表节点b->a,欧了
import java.util.HashMap;
import java.util.List;
import java.util.Stack;
public class Code05_UnionFind {
public static class Node<V> {
V value;
public Node(V v) {
value = v;
}
}
public static class UnionFind<V> {//搞三张表
public HashMap<V, Node<V>> nodes;
public HashMap<Node<V>, Node<V>> parents;//parent表，key是儿子，value是父亲，儿子父亲一一对应
public HashMap<Node<V>, Integer> sizeMap;//代表节点和大小size对应
public UnionFind(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);
}//推出的时候cur = parents.get(cur）
while (!path.isEmpty()) {
parents.put(path.pop(), cur);
}
return cur;
}
public boolean isSameSet(V a, V b) {
return findFather(nodes.get(a)) == findFather(nodes.get(b));
}
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;//就是if（a>b），big=a，small=b
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.表示任务关系，1代表认识，0代表不认识
一定是正方形N*N，且m[i][j]=1,那么m[j][i]=1,大正方形是对称的
求有多少个联通区（朋友圈，互相认识的域）
用并查集，从0开始，0认识2认识4，一合并【0.2.4】，从1开始【1.3】一共两个朋友圈
// 本题为leetcode原题
// 测试链接：https://leetcode.com/problems/friend-circles/
// 可以直接通过
public class Code01_FriendCircles {
public static int findCircleNum(int[][] M) {
int N = M.length;
// 初始化{0} {1} {2} {N-1}每个数据单独成一个集合
UnionFind unionFind = new UnionFind(N);
for (int i = 0; i < N; i++) { //行
for (int j = i + 1; j < N; j++) {//列，for循环只用便利右上部分，因为1认识2，2就认识1
if (M[i][j] == 1) { // i和j互相认识
unionFind.union(i, j);//i，j合并
}
}
}
return unionFind.sets();
}
public static class UnionFind {//用数组代替哈希表，更快
// parent[i] = k ： i的父亲是k
private int[] parent;
// size[i] = k ： 如果i是代表节点，size[i]才有意义，否则无意义
// 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 < N; i++) {
parent[i] = i; //i的父亲节点就是自己
size[i] = 1; //i自己就是代表节点，大小为1
}
}
// 从i开始一直往上，往上到不能再往上，代表节点，返回
// 这个过程要做路径压缩
private int find(int i) {
int hi = 0;
while (i != parent[i]) {//i不等于自己的父亲，i往上
help[hi++] = i;//help作栈
i = parent[i];
}//直到i=parent[i]也就是代表节点了
for (hi--; hi >= 0; hi--) {
parent[help[hi]] = 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[f1] += size[f2];
parent[f2] = f1;
} else {
size[f2] += size[f1];
parent[f1] = f2;
}
sets--;
}
}
public int sets() {
return sets;
}
}
}
岛问题
给定一个二维数组matrix，里面的值不是1就是0
上或下或左或右相邻的1认为是一片岛
返回matrix中岛的数量，求几片1
思路，从左往右依次遍历，不是1就跳过，是一就调用infection函数，把与这个一相邻的1全部变成2，然后往后走不是1就跳
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Stack;
// 本题为leetcode原题
// 测试链接：https://leetcode.com/problems/number-of-islands/
// 所有方法都可以直接通过
public class Code02_NumberOfIslands {
public static int numIslands3(char[][] board) {
int islands = 0;
for (int i = 0; i < board.length; i++) {
for (int j = 0; j < board[0].length; j++) {
if (board[i][j] == '1') {//遍历，是1岛的数量++然后调用感染函数
islands++;
infect(board, i, j);
}
}
}
return islands;
}
// 从(i,j)这个位置出发，把所有练成一片的'1'字符，变成0，不是0字符而是0阿斯克码值
public static void infect(char[][] board, int i, int j) {
if (i < 0 || i == board.length || j < 0 || j == board[0].length || board[i][j] != '1') {
return;
}
board[i][j] = 0;//一定要改，否则无限递归
infect(board, i - 1, j);
infect(board, i + 1, j);
infect(board, i, j - 1);
infect(board, i, j + 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') {//自己是1，右边也是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();
}
}
public static int numIslands2(char[][] board) {
int row = board.length;
int col = board[0].length;
UnionFind2 uf = new UnionFind2(board);
for (int j = 1; j < col; j++) {
if (board[0][j - 1] == '1' && board[0][j] == '1') {
uf.union(0, j - 1, 0, j);
}
}
for (int i = 1; i < row; i++) {
if (board[i - 1][0] == '1' && board[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 (board[i][j] == '1') {
if (board[i][j - 1] == '1') {
uf.union(i, j - 1, i, j);
}
if (board[i - 1][j] == '1') {
uf.union(i - 1, j, i, j);
}
}
}
}
return uf.sets();
}
public static class UnionFind2 {//把二维数组转成一维，对二维数组（i，j）->i*列+j
private int[] parent;
private int[] size;
private int[] help;
private int col;//列
private int sets;//集合数量
public UnionFind2(char[][] board) {
col = board[0].length;
sets = 0;
int row = board.length;
int len = row * col;//一共有几个数
parent = new int[len];
size = new int[len];
help = new int[len];
for (int r = 0; r < row; r++) {//初始化
for (int c = 0; c < col; c++) {
if (board[r][c] == '1') {
int i = index(r, c);
parent[i] = i;
size[i] = 1;
sets++;
}
}
}
}
// (r,c) -> i，用i代替（r，c）
private int index(int r, int c) {//r行c列对应的下标
return r * col + c;
}
// 原始位置 -> 下标
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;
}
public void union(int r1, int c1, int r2, int c2) {
int i1 = index(r1, c1);
int i2 = index(r2, c2);
int f1 = find(i1);
int f2 = find(i2);
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 sets() {
return sets;
}
}
// 为了测试
public static char[][] generateRandomMatrix(int row, int col) {
char[][] board = new char[row][col];
for (int i = 0; i < row; i++) {
for (int j = 0; j < col; j++) {
board[i][j] = Math.random() < 0.5 ? '1' : '0';
}
}
return board;
}
// 为了测试
public static char[][] copy(char[][] board) {
int row = board.length;
int col = board[0].length;
char[][] ans = new char[row][col];
for (int i = 0; i < row; i++) {
for (int j = 0; j < col; j++) {
ans[i][j] = board[i][j];
}
}
return ans;
}
// 为了测试
public static void main(String[] args) {
int row = 0;
int col = 0;
char[][] board1 = null;
char[][] board2 = null;
char[][] board3 = null;
long start = 0;
long end = 0;
row = 1000;
col = 1000;
board1 = generateRandomMatrix(row, col);
board2 = copy(board1);
board3 = copy(board1);
System.out.println("感染方法、并查集(map实现)、并查集(数组实现)的运行结果和运行时间");
System.out.println("随机生成的二维矩阵规模 : " + row + " * " + col);
start = System.currentTimeMillis();
System.out.println("感染方法的运行结果: " + numIslands3(board1));
end = System.currentTimeMillis();
System.out.println("感染方法的运行时间: " + (end - start) + " ms");
start = System.currentTimeMillis();
System.out.println("并查集(map实现)的运行结果: " + numIslands1(board2));
end = System.currentTimeMillis();
System.out.println("并查集(map实现)的运行时间: " + (end - start) + " ms");
start = System.currentTimeMillis();
System.out.println("并查集(数组实现)的运行结果: " + numIslands2(board3));
end = System.currentTimeMillis();
System.out.println("并查集(数组实现)的运行时间: " + (end - start) + " ms");
System.out.println();
row = 10000;
col = 10000;
board1 = generateRandomMatrix(row, col);
board3 = copy(board1);
System.out.println("感染方法、并查集(数组实现)的运行结果和运行时间");
System.out.println("随机生成的二维矩阵规模 : " + row + " * " + col);
start = System.currentTimeMillis();
System.out.println("感染方法的运行结果: " + numIslands3(board1));
end = System.currentTimeMillis();
System.out.println("感染方法的运行时间: " + (end - start) + " ms");
start = System.currentTimeMillis();
System.out.println("并查集(数组实现)的运行结果: " + numIslands2(board3));
end = System.currentTimeMillis();
System.out.println("并查集(数组实现)的运行时间: " + (end - start) + " ms");
}
}
拓展：如果matrix极大 设计一种可行的并行方案
空降问题
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
// 本题为leetcode原题
// 测试链接：https://leetcode.com/problems/number-of-islands-ii/
// 所有方法都可以直接通过
public class Code03_NumberOfIslandsII {
public static List<Integer> numIslands21(int m, int n, int[][] positions) {
UnionFind1 uf = new UnionFind1(m, n);
List<Integer> ans = new ArrayList<>();
for (int[] position : positions) {
ans.add(uf.connect(position[0], position[1]));
}
return ans;
}
public static class UnionFind1 {
private int[] parent;
private int[] size;//区别，变化之后不在抹去size，因为要用size做标记
//size=0代表没有初始化过，没有空降过1
private int[] help;
private final int row;
private final int col;
private int sets;
public UnionFind1(int m, int n) {
row = m;
col = n;
sets = 0;
int len = row * col;
parent = new int[len];
size = new int[len];
help = new int[len];
}
private int index(int r, int c) {
return r * col + c;
}
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) {
if (r1 < 0 || r1 == row || r2 < 0 || r2 == row || c1 < 0 || c1 == col || c2 < 0 || c2 == col) {
return;//检查越界
}
int i1 = index(r1, c1);
int i2 = index(r2, c2);
if (size[i1] == 0 || size[i2] == 0) {
return;
}
int f1 = find(i1);
int f2 = find(i2);
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;
}
}
// 课上讲的如果m*n比较大，会经历很重的初始化，而k比较小，怎么优化的方法
public static List<Integer> numIslands22(int m, int n, int[][] positions) {
UnionFind2 uf = new UnionFind2();
List<Integer> ans = new ArrayList<>();
for (int[] position : positions) {
ans.add(uf.connect(position[0], position[1]));
}
return ans;
}
public static class UnionFind2 {//m*n很大，key相对不大
private HashMap<String, String> parent;//字符串他爹
private HashMap<String, Integer> size;
private ArrayList<String> help;
private int sets;
public UnionFind2() {
parent = new HashMap<>();
size = new HashMap<>();
help = new ArrayList<>();
sets = 0;
}
private String find(String cur) {
while (!cur.equals(parent.get(cur))) {
help.add(cur);
cur = parent.get(cur);
}
for (String str : help) {
parent.put(str, cur);
}
help.clear();
return cur;
}
private void union(String s1, String s2) {
if (parent.containsKey(s1) && parent.containsKey(s2)) {
String f1 = find(s1);
String f2 = find(s2);
if (!f1.equals(f2)) {
int size1 = size.get(f1);
int size2 = size.get(f2);
String big = size1 >= size2 ? f1 : f2;
String small = big == f1 ? f2 : f1;
parent.put(small, big);
size.put(big, size1 + size2);
sets--;
}
}
}
public int connect(int r, int c) {
String key = String.valueOf(r) + "_" + String.valueOf(c);
if (!parent.containsKey(key)) {//之前没空降过的
parent.put(key, key);
size.put(key, 1);
sets++;
String up = String.valueOf(r - 1) + "_" + String.valueOf(c);
String down = String.valueOf(r + 1) + "_" + String.valueOf(c);
String left = String.valueOf(r) + "_" + String.valueOf(c - 1);
String right = String.valueOf(r) + "_" + String.valueOf(c + 1);
union(up, key);
union(down, key);
union(left, key);
union(right, key);
}
return sets;
}
}
}
