首页 > 代码库 > 算法(Algorithms)第4版 练习 1.5.4
算法(Algorithms)第4版 练习 1.5.4
代码实现:
package com.qiusongde; import edu.princeton.cs.algs4.StdIn; import edu.princeton.cs.algs4.StdOut; public class UFWeightedQuickUnion { private int[] id;//parent link(site indexed) private int[] treesize;//size of component for roots(site indexed) private int count;//number of components private static int totalcost = 0;//for the test of array access public UFWeightedQuickUnion(int N) { count = N; id = new int[N]; for(int i = 0; i < N; i++) id[i] = i; treesize = new int[N]; for(int i = 0; i < N; i++) treesize[i] = 1; } 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]; totalcost += 2; } totalcost++; return p; } public void union(int p, int q) { int pRoot = find(p); int qRoot = find(q); if(pRoot == qRoot) return; //make smaller root point to larger one if(treesize[pRoot] < treesize[qRoot]) { id[pRoot] = qRoot; treesize[qRoot] += treesize[pRoot]; totalcost += 5; } else { id[qRoot] = pRoot; treesize[pRoot] += treesize[qRoot]; totalcost += 5; } count--; } @Override public String toString() { String s = ""; for(int i = 0; i < id.length; i++) { s += id[i] + " "; } s += "\n"; for(int i = 0; i < treesize.length; i++) { s += treesize[i] + " "; } s += "\n" + count + " components"; return s; } public static void main(String[] args) { //initialize N components int N = StdIn.readInt(); UFWeightedQuickUnion uf = new UFWeightedQuickUnion(N); StdOut.println(uf); StdOut.println(); while(!StdIn.isEmpty()) { int p = StdIn.readInt(); int q = StdIn.readInt(); if(uf.connected(p, q)) {//ignore if connected StdOut.println(p + " " + q + " is connected"); StdOut.println("totalcost: " + totalcost); StdOut.println(); continue; } uf.union(p, q);//connect p and q StdOut.println(p + " " + q); StdOut.println(uf); StdOut.println("totalcost: " + totalcost); StdOut.println(); } } }
reference input:
10 4 3 3 8 6 5 9 4 2 1 8 9 5 0 7 2 6 1 1 0 6 7
结果:
0 1 2 3 4 5 6 7 8 9 1 1 1 1 1 1 1 1 1 1 10 components 4 3 0 1 2 4 4 5 6 7 8 9 1 1 1 1 2 1 1 1 1 1 9 components totalcost: 9 3 8 0 1 2 4 4 5 6 7 4 9 1 1 1 1 3 1 1 1 1 1 8 components totalcost: 22 6 5 0 1 2 4 4 6 6 7 4 9 1 1 1 1 3 1 2 1 1 1 7 components totalcost: 31 9 4 0 1 2 4 4 6 6 7 4 4 1 1 1 1 4 1 2 1 1 1 6 components totalcost: 40 2 1 0 2 2 4 4 6 6 7 4 4 1 1 2 1 4 1 2 1 1 1 5 components totalcost: 49 8 9 is connected totalcost: 55 5 0 6 2 2 4 4 6 6 7 4 4 1 1 2 1 4 1 3 1 1 1 4 components totalcost: 68 7 2 6 2 2 4 4 6 6 2 4 4 1 1 3 1 4 1 3 1 1 1 3 components totalcost: 77 6 1 6 2 6 4 4 6 6 2 4 4 1 1 3 1 4 1 6 1 1 1 2 components totalcost: 90 1 0 is connected totalcost: 98 6 7 is connected totalcost: 104
worst-case input:
8 0 1 2 3 4 5 6 7 0 2 4 6 0 4
结果:
0 1 2 3 4 5 6 7 1 1 1 1 1 1 1 1 8 components 0 1 0 0 2 3 4 5 6 7 2 1 1 1 1 1 1 1 7 components totalcost: 9 2 3 0 0 2 2 4 5 6 7 2 1 2 1 1 1 1 1 6 components totalcost: 18 4 5 0 0 2 2 4 4 6 7 2 1 2 1 2 1 1 1 5 components totalcost: 27 6 7 0 0 2 2 4 4 6 6 2 1 2 1 2 1 2 1 4 components totalcost: 36 0 2 0 0 0 2 4 4 6 6 4 1 2 1 2 1 2 1 3 components totalcost: 45 4 6 0 0 0 2 4 4 4 6 4 1 2 1 4 1 2 1 2 components totalcost: 54 0 4 0 0 0 2 0 4 4 6 8 1 2 1 4 1 2 1 1 components totalcost: 63
算法(Algorithms)第4版 练习 1.5.4
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。