题目原文:

Add a method find() to the union-find data type so that find(i) returns the largest element in the connected component containing i. The operations, union(), connected(), and find() should all take logarithmic time or better.

 import edu.princeton.cs.algs4.StdIn;
import edu.princeton.cs.algs4.StdOut; public class FindLargestUF {
private int[] id;
private int count;
public FindLargestUF(int n) {
count = n;
id = new int[n];
for (int i = 0; i < n; i++)
id[i] = i;
}
public int count(){
return count;
}
public boolean connected(int p, int q){
return (find(p)==find(q));
}
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);
StdOut.println("find("+p+")="+pRoot+",find("+q+")="+qRoot);
if (pRoot == qRoot)
return;
else if (pRoot < qRoot)
id[pRoot] = qRoot;
else
id[qRoot] = pRoot;
count--;
} public static void main(String[] args) {
int n = StdIn.readInt();
FindLargestUF uf = new FindLargestUF(n);
while (!StdIn.isEmpty()) {
int p = StdIn.readInt();
int q = StdIn.readInt();
if (uf.connected(p, q))
continue;
uf.union(p, q);
StdOut.println("link points:" + p + " " + q);
}
StdOut.println(uf.count() + "components");
}
}

For example, if one of the connected components is {1,2,6,9}, then the find() method should return 9 for each of the four elements in the connected components.

分析:

这一题很简单,要求find到的根是子集中的最大元素。因此只需要在union时,用两个子集中较大的root作为合并后的root就可以了。以下代码提交100

最新文章

  1. (十二)Maven生命周期和插件
  2. 用户名 不在 sudoers文件中
  3. Scala编程--函数式对象
  4. iOS开发零基础--Swift教程 可选类型
  5. oc面向对象特性: 多态
  6. Java8初体验(二)Stream语法详解
  7. OLAT &amp; OLTP
  8. RGui的http代理设置
  9. (剑指Offer)面试题16:反转链表
  10. json网页预览插件
  11. 启用Spring quartz定时器,导致tomcat服务器自动停止
  12. Entity FramWork - 在VS里面直接创建表,并同步到数据库
  13. SAP ABAP exporting list to memory ...SUBMIT 程序传输屏幕参数
  14. Redis客户端管理工具的安装及使用
  15. 【SqlServer系列】集合运算
  16. CentOS 7 如何设置默认启动方式为命令行模式
  17. 自己开发chrome插件生成二维码
  18. NYOJ 一笔画
  19. MVC杂记
  20. java⑧

热门文章

  1. Python三方库xlrd,xlwd-Excel读写
  2. Sandbox 沙盒
  3. mysql存储过程之遍历多表记录后插入第三方表中
  4. javascript 大数据处理方法
  5. Java中接口与接口和类之间的关系
  6. .net core里用ZXing生成二维码
  7. bootstrap table 生成的表格里动态添加HTML元素按钮,JS中添加点击事件,点击没反应---解决办法
  8. 6.shell脚本
  9. 有赞 MySQL 自动化运维之路 — ZanDB
  10. 【解题报告】 Leapin&#39; Lizards HDU 2732 网络流