QuickFind-【Princeton-Robert Sedgewick】アルゴリズム
1100 ワード
コードは基本的にノックして、QuickFindアルゴリズムをテストします
<span style="font-size:14px;">package quickFind;
import java.util.Scanner;
public class QF {
private int[] id;
public QF(int N){
id = new int[N];
for(int i = 0; i < N; i++){
id[i] = i;//set id of each object to itself
}
}
public boolean connected(int p, int q) //check whether p and q are in the same component
{ return id[p] == id[q]; }
public void union(int p, int q) //change all entries with id[p] to id[q]
{
int pid = id[p];
int qid = id[q];
for(int i = 0; i < id.length; i++)
if(id[i] == pid) id[i] = qid;
}
public static void main(String args[]){
Scanner s = new Scanner(System.in);
int N = s.nextInt();
QF qf = new QF(N);
int count = 0;
while(++count < N)
{
int p = s.nextInt();
int q = s.nextInt();
if(!qf.connected(p, q))
{
qf.union(p, q);
System.out.println(p + " " + q);
}
}
for(int i = 0; i < N; i++)
System.out.print(qf.id[i] + " ");
System.out.println();
s.close();
}
}</span>