美文网首页
并查集 C++ / java代码

并查集 C++ / java代码

作者: 东京的雨不会淋湿首尔 | 来源:发表于2021-07-26 21:06 被阅读0次

    c++:

    class UnionFind{
        vector<int> root; // 根节点
        vector<int> rank; // 节点高度
    public:
        UnionFind(int size){
            root.resize(size);
            rank.resize(size);
            for(int i=0;i<size;++i){
                root[i]=i;
                rank[i]=1;
            }
        }
        void unionNum(int x,int y){
            int rootX=find(x);
            int rootY=find(y);
            // 两个根节点相等的话啥也不干,不相等则union
            if(rootX!=rootY){
                if(rank[rootX]>rank[rootY]){
                    root[rootY]=rootX;
                }else if(rank[rootX]<rank[rootY]){
                    root[rootX]=rootY;
                }else{
                    root[rootY] = rootX;
                    rank[rootX]++;
                }
            }
        }
        int find(int x){
            if(x==root[x]){
                return x;
            }
            return root[x]=find(root[x]);
        }
    
        bool connect(int x, int y){
            return find(x)==find(y);
        }
    }
    

    java:

    // UnionFind.class
    public class UnionFind {
        int root[];
        // 添加了 rank 数组来记录每个顶点的高度,也就是每个顶点的「秩」
        int rank[];
    
        public UnionFind(int size) {
            root = new int[size];
            rank = new int[size];
            for (int i = 0; i < size; i++) {
                root[i] = i;
                rank[i] = 1; // 一开始每个顶点的初始「秩」为1,因为它们只有自己本身的一个顶点。
            }
        }
    
            // 此处的 find 函数与路径压优化缩版本的 find 函数一样。
        public int find(int x) {
            if (x == root[x]) {
                return x;
            }
            return root[x] = find(root[x]);
        }
    
            // 按秩合并优化的 union 函数
        public void union(int x, int y) {
            int rootX = find(x);
            int rootY = find(y);
            if (rootX != rootY) {
                if (rank[rootX] > rank[rootY]) {
                    root[rootY] = rootX;
                } else if (rank[rootX] < rank[rootY]) {
                    root[rootX] = rootY;
                } else {
                    root[rootY] = rootX;
                    rank[rootX] += 1;
                }
            }
        };
    
        public boolean connected(int x, int y) {
            return find(x) == find(y);
        }
    }
    
    // App.java
    // 测试样例
    public class App {
        public static void main(String[] args) throws Exception {
            UnionFind uf = new UnionFind(10);
            // 1-2-5-6-7 3-8-9 4
            uf.union(1, 2);
            uf.union(2, 5);
            uf.union(5, 6);
            uf.union(6, 7);
            uf.union(3, 8);
            uf.union(8, 9);
            System.out.println(uf.connected(1, 5)); // true
            System.out.println(uf.connected(5, 7)); // true
            System.out.println(uf.connected(4, 9)); // false
            // 1-2-5-6-7 3-8-9-4
            uf.union(9, 4);
            System.out.println(uf.connected(4, 9)); // true
        }
    }
    

    相关文章

      网友评论

          本文标题:并查集 C++ / java代码

          本文链接:https://www.haomeiwen.com/subject/rgtamltx.html