1. 概念

并查集（Union Find）是一种树型的数据结构，用于处理一些不相交集合（Disjoint Sets）的合并及查询问题。常常在使用中以森林来表示。

功能：

a. 查找两个元素是否属于同一个集合:isSameSet(A,B) A所在的集合为Set1，B所在的集合为Set2，则返回Set1和Set2是否属于同一个集合；

b. 将两个元素各自所在的集合合并到一起

class UnionFind {
    public static class Node{
        //whataver you like
        int x, y;
        public Node(int x, int y){
            this.x = x;
            this.y = y;
        }
    }
    public static class unionFindSet{
        public HashMap<Node, Node> fatherMap;
        public HashMap<Node, Integer> sizeMap;
        public unionFindSet(List<Node> nodes){
            makeSets(nodes);
        }
        private void makeSets(List<Node> nodes){
            fatherMap = new HashMap<>();
            sizeMap = new HashMap<>();
            for(Node node : nodes){
                fatherMap.put(node, node);
                sizeMap.put(node, 1);
            }
        }
        private Node findHead(Node node){   //找到代表节点,并扁平优化集合结构
            Stack<Node> stack = new Stack<>();
            Node curr = node;
            Node parent = fatherMap.get(curr);
            while(curr != parent){
                stack.push(node);
                curr = parent;
                parent = fatherMap.get(curr);
            }
            while (!stack.isEmpty()){
                fatherMap.put(stack.pop(), parent);
            }
            return parent;
        }
        //如果说父节点一样，那么就是同一个集合
        public boolean isSameSet(Node a, Node b){
            return findHead(a) == findHead(b);
        }

        public void union(Node a, Node b){
            if(a == null || b == null){
                return;
            }
            Node aHead = findHead(a);
            Node bHead = findHead(b);
            if(aHead != bHead){
                int aSetSize = sizeMap.get(aHead);
                int bSetSize = sizeMap.get(bHead);
                if(aSetSize <= bSetSize){
                    fatherMap.put(aHead, bHead);
                    sizeMap.put(bHead, aSetSize + bSetSize);
                }else{
                    fatherMap.put(bHead, aHead);
                    sizeMap.put(aHead, aSetSize + bSetSize);
                }
            }
        }
    }
}

2. 例题

（1）leetcode1202

交换字符串中的元素

class Solution {
    public String smallestStringWithSwaps(String s, List<List<Integer>> pairs) {
//由于交换关系的传递性，pairs中的索引可以按照相连性分成组，这个组之内的所有字符可以直接排序
//s = "dcab", pairs = [[0,3],[1,2],[0,2]],  0,1,2,3位置上的元素可以任意排序，因此是abcd
//s = "dcab", pairs = [[0,3],[1,2]],    0,3一组任意排序,1，2一组任意排序
        if(pairs.size() == 0){
            return s;
        }
        int len = s.length();
        //构建并查集
        UnionFind union = new UnionFind(len);
        for(int i = 0; i < pairs.size(); i++){
            int index0 = pairs.get(i).get(0);
            int index1 = pairs.get(i).get(1);
            union.union(index0, index1);
        }

        Map<Integer, PriorityQueue<Character>> map = new HashMap<>();
        for(int i = 0; i < len; i ++){
            int head = union.findHead(i);
            if(!map.containsKey(head)){
                map.put(head, new PriorityQueue<Character>());
            }
            map.get(head).add(s.charAt(i));
        }
        
        StringBuilder sb = new StringBuilder();
        for(int i = 0; i < len; i++){
            sb.append(map.get(union.findHead(i)).poll());
        }
        return sb.toString();
    }
}
class UnionFind{
    int[] parent;
    int[] rank;
    public UnionFind(int n){
        this.parent = new int[n];
        this.rank = new int[n];
        for(int i = 0; i < n; i++){
            parent[i] = i;
            rank[i] = 1;
        }
    }
    //加入同一个集合
    public void union(int x, int y){
        int rootx = findHead(x);
        int rooty = findHead(y);
        if(rootx == rooty){
            return;
        }
        if(rank[rootx] == rank[rooty]){
            parent[rootx] = rooty;
            rank[rooty] ++;
        }else if(rank[rootx] < rank[rooty]){
            parent[rootx] = rooty;
        }else{
            parent[rooty] = rootx;
        }
    }
    public int findHead(int x){
        if(x != parent[x]){
            parent[x] = findHead(parent[x]);
        }
        return parent[x];
    }
}

（2）leetcode200岛屿数量

岛屿数量

//并查集，不需要rank
class Solution {
    public int numIslands(char[][] grid) {
        int rows = grid.length;
        int cols = grid[0].length;
        UnionFind union = new UnionFind(rows, cols);
        Set<Integer> set = new HashSet<>();
        for(int i = 0; i < rows; i++){
            for(int j = 0; j < cols; j++){
                if(grid[i][j] == '1'){
                    if(i >= 1 && grid[i - 1][j] == '1'){//up
                        union.union(i, j, i - 1, j);
                    }
                    if(j >= 1 && grid[i][j - 1] == '1'){//left
                        union.union(i, j, i, j - 1);
                    }
                }
            }
        }
        for(int i = 0; i < rows; i++){
            for(int j = 0; j < cols; j++){
                if(grid[i][j] == '1'){
                    set.add(union.findHead(i, j));
                }
            }
        }
        return set.size();
    }
}
class UnionFind{
    int[] parent;
    int rows;
    int cols;
    public UnionFind(int rows, int cols){
        this.rows = rows;
        this.cols = cols;
        this.parent = new int[rows * cols];
        for(int i = 0; i < rows; i ++){
            for(int j = 0; j < cols; j ++){
                parent[cols * i + j] = cols * i + j;
            }
        }
    }
    //加入同一个集合
    public void union(int x1, int y1, int x2, int y2){
        int root1 = findHead(x1, y1);
        int root2 = findHead(x2, y2);
        if(root1 == root2){
            return;
        }
        parent[root1] = root2;
    }
    public int findHead(int x, int y){
        int index = this.cols * x + y;
        if(index != parent[index]){
            int row = parent[index] / cols;
            int col = parent[index] % cols;
            parent[index] = findHead(row, col);
        }
        return parent[index];
    }
}