模板

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