算法第四版1.5union-find：习题1.5.17

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了算法第四版1.5union-find：习题1.5.17，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含1755字，纯文字阅读大概需要3分钟。

内容图文

import edu.princeton.cs.algs4.StdIn;
import edu.princeton.cs.algs4.StdOut;

public class E1_5_17 {
    public static void main(String[]args){
        int N= StdIn.readInt();
        int cnt=RandomConnection.count(N);
        StdOut.printf("N=%8d  count=%15d\n",N,cnt);
    }
}

 

import edu.princeton.cs.algs4.StdRandom;

public class RandomConnection {
    public static int count(int N){
        //Union find.随机产生pair,直到所有点连在一起，返回产生的数的个数
        WeightedQuickUnionUF uf=new WeightedQuickUnionUF(N);
        int cnt=0;
        while (uf.count()!=1){
            int p= StdRandom.uniform(0,N);
            int q=StdRandom.uniform(0,N);
            uf.union(p,q);//函数中会判断是否已经连接
            cnt+=2;
        }
        return cnt;
    }
}

import edu.princeton.cs.algs4.StdIn;
import edu.princeton.cs.algs4.StdOut;

public class WeightedQuickUnionUF {
    public static void main(String[]args){
        //Solve dynamic connectivity problem on StdIn.
        int N= StdIn.readInt();
        WeightedQuickUnionUF uf=new WeightedQuickUnionUF(N);
        while (!StdIn.isEmpty()){
            int p=StdIn.readInt();
            int q=StdIn.readInt();
            if (uf.connected(p,q))continue;
            uf.union(p,q);
            StdOut.println(p+"  "+q);
        }
        StdOut.println(uf.count()+" components");
    }

    private int[]id; //parent link(site indexed)
    private int[]sz; //size of component for roots(site indexed) 只有根节点存储的是树的大小
    private int count;//number of component
    public WeightedQuickUnionUF(int N){
        count=N;
        id=new int[N];
        for (int i=0;i<N;i++)   id[i]=i;
        sz=new int[N];
        for (int i=0;i<N;i++)   sz[i]=1;
    }
    public int count(){
        return count;
    }
    public boolean connected(int p,int q){
        return find(p)==find(q);
    }
    public int find(int p){
        //Follow links to find a root.
        while (p!=id[p])p=id[p];
        return p;
    }
    public void union(int p,int q){
        int i=find(p);
        int j=find(q);
        if (i==q)return;
        //Make smaller root point to large one.
        if (sz[i]<sz[j]){id[i]=j;sz[j]+=sz[i];}
        else            {id[j]=i;sz[i]+=sz[j];}
        count--;
    }
}

 

内容总结

以上是互联网集市为您收集整理的算法第四版1.5union-find：习题1.5.17全部内容，希望文章能够帮你解决算法第四版1.5union-find：习题1.5.17所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

---