并查集

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];
    }
}

（3）leetcode484冗余连接

冗余连接

class Solution {
    public int[] findRedundantConnection(int[][] edges) {
// 并查集
        Set<Integer> set = new HashSet<>();
        for(int[] edge : edges){
            set.add(edge[0]);
            set.add(edge[1]);
        }
        int len = edges.length;
        boolean[] visited = new boolean[len];
        UnionFind uf = new UnionFind(set);
        for(int i = 0; i < len; i++){
            int[] edge = edges[i];
            int root1 = uf.findHead(edge[0]);
            int root2 = uf.findHead(edge[1]);
            if(root1 != root2){
                visited[i] = true;
                uf.union(root1, root2);
            }
        }
        for(int i = len - 1; i >= 0; i--){
            if(!visited[i]){
                return edges[i];
            }
        }
        return new int[]{};
    }
}
class UnionFind{
    Map<Integer, Integer> parent;
    public UnionFind(Set<Integer> set){
        parent = new HashMap<>();
        for(int i : set){
            parent.put(i, i);
        }
    }
    public void union(int i, int j){
        int rooti = findHead(i);
        int rootj = findHead(j);
        parent.put(rootj, rooti);
    }
    public int findHead(int i){
        int father = parent.get(i);
        if(i != father){
            father = findHead(father);
        }
        return father;
    }
}

（4）leetcode1584连接所有点的最小费用

连接所有点的最小费用

// 并查集
class Solution {
    public int minCostConnectPoints(int[][] points) {
        int n = points.length;//点的个数
        UnionFind uf = new UnionFind(n);
        List<Edge> edges = new ArrayList<>();
        for(int i = 0; i < n; i++){
            for(int j = i + 1; j < n; j++){
                edges.add(new Edge(dist(points, i, j), i, j));
            }
        }
        // 把所有边按照长度从小到大进行排序
        Collections.sort(edges, (edge1, edge2) -> (edge1.len - edge2.len));
        int minCost = 0, edgeNum = 1;
        for(Edge edge : edges){
            int len = edge.len;
            int p1 = edge.x;
            int p2 = edge.y;
            if(uf.union(p1, p2)){
                minCost += len;
                edgeNum ++;
                if(edgeNum == n){
                    break;
                }
            }
        }
        return minCost;
    }
    public int dist(int[][] points, int i, int j){
        return Math.abs(points[i][0] - points[j][0]) + 
        Math.abs(points[i][1] - points[j][1]);
    }
}
class UnionFind{
    int[] parent;
    int[] rank;
    int n;
    public UnionFind(int n){
        this.n = n;
        parent = new int[n];
        rank = new int[n];
        Arrays.fill(rank, 1);
        for(int i = 0; i < n; i++){
            parent[i] = i;
        }
    }
    public int findHead(int i){
        if(i != parent[i]){
            parent[i] = findHead(parent[i]);
        }
        return parent[i];
    }
    // 这里设置为boolean是为了题目的需要
    public boolean union(int x, int y){
        int rootx = findHead(x);
        int rooty = findHead(y);
        if(rootx == rooty){
            return false;
        }
        if(rank[rootx] < rank[rooty]){
            // 交换
            int temp = rank[rootx];
            rank[rootx] = rank[rooty];
            rank[rooty] = temp;
        }
        // 扁平化树形结构
        rank[rootx] += rank[rooty];
        parent[rooty] = parent[rootx];
        return true;
    }
}
class Edge{
    int len, x, y;
    public Edge(int len, int x, int y){
        this.len = len;
        this.x = x;
        this.y = y;
    }
}