最近在看《算法(第四版)》,里面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循环无法结束导致的,那么应当如何调整才能使程序正常结束

解决方案 »

  1.   

    老哥,我猜的,看见你的readerInt(),读行是需要关流的的。
      

  2.   

    那么怎样设置while的条件,以在合适的时机关流呢
    是从外部输入文件,文件内是节点数目和要连接的几对变量:
    就像这样:
    10
    4 3
    3 8
    6 5
    9 4
    2 1
    8 9
    5 0
    7 2
    6 1
    1 0
    6 7
      

  3.   

    uf.close();
      

  4.   

    break;