Algs4-1.5.2使用quick-union算法完成练习1.5.1

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了Algs4-1.5.2使用quick-union算法完成练习1.5.1，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含1741字，纯文字阅读大概需要3分钟。

内容图文

1.5.2使用quick-union算法(请见1.5.2.3节代码框)完成练习1.5.1。另外，在处理完输入的每对整数之后画出id[]数组表示的森林。
答：








public class UF
{
??? private int[] id;
??? private int count;
??? public UF(int N)
??? {
??????? count=N;
??????? id=new int[N];
??????? for (int i=0;i<N;i++)
??????? {
??????????? id[i]=i;
????????? StdOut.printf("%3d",i);
??????? }
??????? StdOut.println();
??? }
???
???? public int count()
???? {return count;}
????
????? boolean connected(int p,int q)
????? {return find(p)==find(q);}
???? /*quick-find
?????? public int find(int p)
?????? {return id[p];}
??????
?????? public? void union(int p,int q)
?????? {
????????? int pID=find(p);
????????? int qID=find(q);
????????? if (pID==qID) return;
????????? for (int i=0;i<id.length;i++)
????????????? if(id[i]==pID) id[i]=qID;
????????? count--;
????????? for (int i=0;i<id.length;i++)
????????????? StdOut.printf("%3d",id[i]);
????????? StdOut.println();
?????? }
????? */

????? public int find(int p)
????? {
????????? while(p!=id[p]) p=id[p];
????????? return p;
????? }
?????
????? public void union(int p,int q)
????? {
????????? int pRoot=find(p);
????????? int qRoot=find(q);
????????? if(pRoot==qRoot) return;
????????? id[pRoot]=qRoot;
????????? count--;
????????? //
?????????? for (int i=0;i<id.length;i++)
????????????? StdOut.printf("%3d",id[i]);
????????? StdOut.println();
????? }

?????? public static void main(String[] qrgs)
?????? {
?????????? int N=StdIn.readInt();
?????????? UF uf=new UF(N);
?????????? while (!StdIn.isEmpty())
?????????? {
?????????????? int p=StdIn.readInt();
?????????????? int q=StdIn.readInt();
?????????????? if(uf.connected(p,q)) continue;
?????????????? StdOut.println(p+ " " +q);
?????????????? uf.union(p,q);
??????????????
??????????? }//end while
??????? }//end main
}//end class

内容总结

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

内容备注

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

内容手机端

---