9. 并查集

思想概述

并查集是一种树型的数据结构，用于处理一些不相交集合的合并及查询问题。 并查集的思想是用一个数组表示了整片森林（parent），树的根节点唯一标识了一个集合，我们只要找到了某个元素的的树根，就能确定它在哪个集合里

重要思想：用集合中的一个元素代表整个集合，一个代表节点，代表整个集合。

常用于解决图的连通性问题！

并查集维持了一大堆集合的结构，把所有的小样本都建成集合。支持集合合并和查询的一个结构。

操作1. 查询两个样本是否在一个集合中，boolean isSameSet(a,b)
操作2. 两个样本所在集合的全体合并为一个集合，void union(a, b)

一共有N个样本，调用 isSameSet和union两个方法非常频繁，最后平均调用方法的时间复杂度为常数级别O(1)

eg: 有一百万个样本，频繁执行上述两个操作，频繁的执行次数超过一百万次，那么单次查询的平均时间为常数级别。

并查集的设计思想如下：

如下，每个集合中只有一个值，每个元素都有一个指针，以下集合中只有一个元素，元素指针指向自己。

对于操作1查询两个样本是否在一个集合中执行逻辑如下：
检查1所在的集合和2所在的集合是否在同一个集合，1向上查询不能再向上的节点为自己1，同样2执行同样操作查到2，此时的1和2称之为集合的代表节点，代表节点不同，则1所在的集合和2所在的集合不是同一集合。

对于操作2两个样本所在集合的全体合并为一个集合的执行逻辑如下：
将1所在的集合和2所在的集合全体合并为一个集合，分别找到元素1和2所在集合的代表节点分别为1，2。然后将2元素的指针向上指向1元素。此时就完成了集合的合并，合并之后1和2所在集合的代表节点为1。（小的挂在大的上面）。如图，集合3和1合并，

—>
集合4，5，6合并

集合4和集合1合并,最后形成一个树形结构
—>

结论：
一开始所有的样本量为N，findHead()操作到达了O(N)或者是超过了O(N)，也就是说，这个操作很频繁。那么均摊下来，单次findHead()的平均时间复杂度为O(1)常数级别的。

并查集结构Map实现

// 对V类型的数据进行封装
public static class Node<V> {
    V value;  // V样本类型
    public Node(V v) {
        value = v;
    }
}
public static class UnionFindSet<V> {
    public HashMap<V, Node<V>> nodes;         // 样本与样本加工后带圈的结构一一对应，相当于对基本数据类型的封装
    public HashMap<Node<V>, Node<V>> parents; // 代替指针的作用。记录每个节点的直系父节点 key 为节点，value为父节点
    public HashMap<Node<V>, Integer> sizeMap;  // 存储集合的大小，key为代表节点，value为该集合的大小。只有代表节点才会存储在这里。
    // 并查集初始化，将所有的样本每个都建成一个小集合
    public UnionFindSet(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);
        }
    }
    // 给你一个节点，请你往上查找父节点到不能再往上，把代表节点返回
    // 当findHead方法的调用频率达到或者超过O(N)，那么该方法的时间复杂度就是O(1)
    public Node<V> findHead(Node<V> cur) {
        Stack<Node<V>> path = new Stack<>();
        while (cur != parents.get(cur)) {
            path.push(cur);
            cur = parents.get(cur);
        }
        // 优化2-返回之前进行优化，栈中元素弹出，修改父节点，扁平处理
        while (!path.isEmpty()) {
            parents.put(path.pop(), cur);
        }
        return cur;
    }
    // 并查集 操作1-查询两个样本是否在一个集合中
    public boolean isSameSet(V a, V b) {
        return findHead(nodes.get(a)) == findHead(nodes.get(b));
    }
    // 并查集 操作2-两个样本所在集合的全体合并为一个集合
    public void union(V a, V b) {
        Node<V> aHead = findHead(nodes.get(a));  // 查找a的代表节点
        Node<V> bHead = findHead(nodes.get(b));  // 查找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;
            // 优化1-小集合的头的父节点指向大集合的头
            parents.put(small, big);
            sizeMap.put(big, aSetSize + bSetSize);
            sizeMap.remove(small);// 删除小集合
        }
    }
    public int sets() {
        return sizeMap.size();
    }
}

并查集结构数组实现

public static class UnionFindSet {
    // 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 UnionFindSet(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;
            size[i] = 1;
        }
    }
    // 从i开始一直往上，往上到不能再往上，代表节点，返回
    // 同时这个过程要做路径压缩
    private int findHead(int i) {
        int hi = -1;
        while (i != parent[i]) {
            help[++hi] = i;
            i = parent[i];
        }
        while(hi>=0) {
            parent[help[hi]] = i;
        }
        return i;
    }
    public void union(int i, int j) {
        int f1 = findHead(i);
        int f2 = findHead(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;
    }
}

题目1： 岛屿数量

LeetCode 200 https://leetcode-cn.com/problems/number-of-islands/

给你一个由 ‘1’（陆地）和 ‘0’（水）组成的的二维网格，请你计算网格中岛屿的数量。 岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。 此外，你可以假设该网格的四条边均被水包围。

输入：grid = [
["1","1","1","1","0"],
["1","1","0","1","0"],
["1","1","0","0","0"],
["0","0","0","0","0"]
]
输出：1

解法一：递归感染的方式

 // 时间复杂度为O(M*N) mn为二维数组的行和列
// 在主流程中每个位置只会走一遍，对于每个位置，最多只会被自己的上下左右四个邻居调用依次infect。总流程，每个节点最多只会遍历5遍。时间复杂度5*O(M*N)
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') {
                islands++;
                infect(board, i, j);
            }
        }
    }
    return islands;
}

// 从(i,j)这个位置出发，把所有连成一片的'1'字符，变成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);
}

方式二：并查集

class Solution {
    public int numIslands(char[][] board) {
        // 初始化操作
        UnionFindSet unionSet = new UnionFindSet(board);
        // 先对以一行的数据进行union
        for (int i = 0, j = 1; j < board[0].length; j++) {
            if(board[0][j-1] == '1' && board[0][j] == '1'){
                unionSet.union(0,j-1,0,j);
            }
        }
        // 先对以一列的数据进行union
        for (int i = 1, j = 0; i < board.length; i++) {
            if(board[i-1][0] == '1' && board[i][0] == '1'){
                unionSet.union(i-1,0,i,0);
            }
        }
        // 然后对剩下的进行统一处理
        for(int i = 1; i < board.length; i++){
            for(int j = 1; j < board[0].length; j++){
                if(board[i-1][j] == '1' && board[i][j] == '1'){
                    unionSet.union(i-1,j,i,j);
                }
                if(board[i][j-1] == '1' && board[i][j] == '1'){
                    unionSet.union(i,j-1,i,j);
                }
            }
        }
        return unionSet.getSets();
    }
    // 并查集使用数组来实现
    public class UnionFindSet{
        private int[] parents;
        private int[] size;
        private int[] help;
        private int col;  // 列号
        private int sets;
        public UnionFindSet(char[][] board) {
            // 对board进行处理
            int row = board.length;
            col = board[0].length;
            int len = row * col;

            parents = new int[len];
            size = new int[len];
            help = new int[len];
            sets = 0;
            for(int i = 0; i < row; i++){
                for(int j = 0; j < col; j++){
                    if(board[i][j] == '1'){
                        int value = index(i,j);
                        parents[value] = value;
                        size[value] = 1;
                        sets++;
                    }
                }
            }
        }
        // getIndex
        public int index(int i, int j){
            return i * col + j;
        }
        // getHead
        public int getHead(int i, int j){
            int cur = index(i,j);
            int h = -1;
            while(cur != parents[cur]){
                help[++h] = cur;
                cur = parents[cur];
            }
            // 扁平化处理
            while(h >=0 ){
                parents[help[h--]] = cur;
            }
            return cur;
        }
        // union
        public void union(int r1, int c1, int r2, int c2){
            int a = getHead(r1,c1);
            int b = getHead(r2,c2);
            if(a != b){
                if(size[a]<=size[b]){
                    parents[a] = b;
                    size[b]+=size[a];
                } else {
                    parents[b] = a;
                    size[a]+=size[b];
                }
                sets--;
            }
        }
        public int getSets(){
            return sets;
        }
    }
}

题目2： 岛屿问题II

/**
 * 岛屿问题的变形2
 * 给定一个mxn的数组，初始化数组都是0，然后动态地修改该数组中不同位置的值，求经过一系列修改之后最大的岛屿数
 */
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;
        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) {  // 第一次修改为1时
                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 {
        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;
        }
    }
}

题目3：省份统计、朋友圈

// 本题为leetcode原题 547  省份或者朋友圈的问题
// https://leetcode-cn.com/problems/number-of-provinces/
// 测试链接：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}
        UnionFindSet unionFind = new UnionFindSet(N);// 并查集初始化
        for (int i = 0; i < N; i++) { // 对称矩阵，只遍历右上半区即可  i表示行号，j表示列号。
            for (int j = i + 1; j < N; j++) {
                if (M[i][j] == 1) { // i和j互相认识
                    unionFind.union(i, j);  // 合并以ij为代表节点的集合
                }
            }
        }
        return unionFind.sets();
    }

    /**
     *  数组方式实现并查集
     */
    public static class UnionFindSet {
        // 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 UnionFindSet(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;
                size[i] = 1;
            }
        }

        // 从i开始一直往上，往上到不能再往上，代表节点，返回
        // 同时这个过程要做路径压缩
        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 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;
        }
    }

}