[SWEA] 3289. 서로소 집합

import java.util.ArrayList;
import java.util.Scanner;


public class Solution {

	static int n, m; 
	static int[] p;
	static int[] rank;
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		int T = sc.nextInt();
		
		for(int tc=1; tc<=T; tc++) {
			n = sc.nextInt();
			m = sc.nextInt();
			p = new int[n+1];
			rank = new int[n+1];
			
			System.out.print("#" + tc + " ");
			
			for(int i=1; i<n; i++) makeSet(i);			
			
			for(int i=0; i<m; i++) {
				int op = sc.nextInt();
				int a = sc.nextInt();
				int b = sc.nextInt();
				
		
				if(op == 0) { // 합집합 연산
					union(a, b);
				} else if(op == 1) { // 같은 집합에 포함되어 있는지 확인하는 연산
					if(findSet(a) == findSet(b))
						System.out.print(1);
					else System.out.print(0);
				}
				
			}
			System.out.println();
		}
	}
	
	
	public static void makeSet(int x) {
		p[x] = x; // 부모를 자신의 index로 표기
//		rank[x] = 0; // 깊이 저장, 초기값이 0임
	}
	
	
	/** 일반멤버 x를 포함하는 집합의 대표자 index 를 리턴 */
	public static int findSet(int x) {
		if(p[x] == x) return x;
		else {
			p[x] = findSet(p[x]); // Path Compression
			return p[x];			
		}
	}
	
	/** 일반 멤버 x, 일반 멤버 y를 포함하는 두 집합을 통합 */
	public static void union(int x, int y) {
		int px = findSet(x);
		int py = findSet(y);
		
		if(px != py) { // 다른 집합일 때만 합치기, 같은 집합인데 합치면 StackOverflowError
			link(px, py);
		}
	}
	
	/** x의 대표자 집합과 y의 대표자집합을 rank 값을 기준으로 합침 - 깊은 쪽을 대표자로 설정 */
	public static void link(int px, int py) {
		if(rank[px] > rank[py]) {
			p[py] = px;
		} else { // rank[px] <= rank[py]
			p[px] = py;
			if(rank[px] == rank[py]) { // 깊이가 같은 경우 랭크값을 증가시켜준다.
				rank[py]++;
			}
		}
	}
}