QuickFind-【Princeton-Robert Sedgewick】アルゴリズム


コードは基本的にノックして、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>