最近在看《算法(第四版)》,里面1-5提到的加权quick-find算法,代码如下:
package com.WeightedQuickUnionUF;import edu.princeton.cs.algs4.StdIn;
import edu.princeton.cs.algs4.StdOut;public class WeightedQuickUnionUF { private int[] id;
private int[] sz;
private int count;
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){
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 == j){
return;
}
if(sz[i] < sz[j]){
id[i] = j;
sz[j] += sz[i];
}else{
id[j] = i;
sz[i] += sz[j];
}
count --;
}
public static void main(String[] args) {
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");
}
}
在运行时无法输出最后的StdOut.println(uf.count() + "components");,查阅资料了解到这是因为while循环无法结束导致的,那么应当如何调整才能使程序正常结束
package com.WeightedQuickUnionUF;import edu.princeton.cs.algs4.StdIn;
import edu.princeton.cs.algs4.StdOut;public class WeightedQuickUnionUF { private int[] id;
private int[] sz;
private int count;
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){
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 == j){
return;
}
if(sz[i] < sz[j]){
id[i] = j;
sz[j] += sz[i];
}else{
id[j] = i;
sz[i] += sz[j];
}
count --;
}
public static void main(String[] args) {
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");
}
}
在运行时无法输出最后的StdOut.println(uf.count() + "components");,查阅资料了解到这是因为while循环无法结束导致的,那么应当如何调整才能使程序正常结束
是从外部输入文件,文件内是节点数目和要连接的几对变量:
就像这样:
10
4 3
3 8
6 5
9 4
2 1
8 9
5 0
7 2
6 1
1 0
6 7