并查集

作者: senzx | 来源:发表于2021-04-26 20:04 被阅读0次

模板

class Union{
    private int[] parent;
    private double[] weight;
    private int[] rank;
    int count;

    public Union(int n){
        parent = new int[n];
        weight = new double[n];
        rank = new int[n];
        for(int i=0;i<n;i++){
            parent[i]=i;
            weight[i]=1.0;
            rank[i]=1;
        }
        count=n;
    }

    public void union(int p, int q, double w){
        int rootP = find(p);
        int rootQ = find(q);
        if(rootP==rootQ){
            return;
        }
        if(rank[rootP]>rank[rootQ]){
            int temp = rootP;
            rootP = rootQ;
            rootQ = temp;
        }
        parent[rootP]=rootQ;
        weight[rootP]= w * weight[q] / weight[p];
        rank[rootQ] += rank[rootQ];
        count--;
    }

    public double isConnected(int p, int q){
        int rootP = find(p);
        int rootQ = find(q);
        if(rootP!=rootQ){
            return -1.0;
        }else{
            return weight[p]/weight[q];
        }
    }

    /**
        递归
    */
    public int find1(int p){
        if(parent[p]!=p){
            int origin = parent[p];
            parent[p] = find(origin);
            weight[p] = weight[p] * weight[origin];
        }
        return parent[p];
    }

    /**
        迭代
    */
    public int find(int p){
        int root = p;
        double w = 1;
        while(parent[root]!=root){
            w *= weight[root];
            root = parent[root];
        }

        int x = p;
        while(x!=root){
            int originFather = parent[x];
            double originWeight = weight[x];
            parent[x] = root;
            weight[x] = w;
            w /= originWeight;
            x = originFather;
        }

        return root;
    }
}

相关文章

  • markdown学习

    #并查集 ##并查集的定义 ##并查集的操作

  • 算法模板(四)并查集

    并查集 路径压缩并查集

  • 并查集入门使用

    本文参考自《算法笔记》并查集篇 并查集的定义 什么是并查集?并查集可以理解为是一种维护数据集合的结构。名字中并查集...

  • 并查集练习

    并查集 参考《算法笔记》 三要素:并,查,集。 并差集与一个算法有关,kruskal算法,就可通过并查集实现。 1...

  • 并查集

    并查集 并查集是什么 并查集是一种用来管理元素分组情况的数据结构,并查集可以高效地进行如下操作: 查询元素a和元素...

  • 数据结构与算法(十二)并查集(Union Find)

    本文主要包括以下内容: 并查集的概念 并查集的操作 并查集的实现和优化Quick FindQuick Union基...

  • 并查集

    并查集是什么 并查集是一种用来管理元素分组情况的数据结构。并查集可以高效地进行如下操作。不过需要注意并查集虽然可以...

  • 并查集

    开始时让每个元素构成一个个单元素集合(注意初始化时应使每个元素各成一组)按照一定顺序将属于同一组元素所在的集合合并...

  • 并查集

  • 并查集

    并查集 https://blog.csdn.net/liujian20150808/article/details...

网友评论

      本文标题:并查集

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