[swexpert] 3289. 서로소 집합 (java, union-find 함수)

 

import java.util.Scanner;

public class Solution {
	static int t,n,m;
	
	public static void main(String[] args) {
		Scanner sc=new Scanner(System.in);
		t=sc.nextInt();
		for (int tc = 1; tc <=t; tc++) {
			n=sc.nextInt();
			m=sc.nextInt();
			int parent[]=new int[n+1];
			for(int i=1;i<=n;i+=1) {
				parent[i]=i;
			}
			System.out.print("#"+tc+" ");
			for (int i = 0; i < m; i++) {
				int command=sc.nextInt();
				int a=sc.nextInt();
				int b=sc.nextInt();
				if(command==1) {
					if(find(parent,a,b)) {
						System.out.print("1");
					}else {
						System.out.print("0");
					}
				}else {
					union(parent,a,b);
				}
			}
			System.out.println();
		}
	}
	public static int findSet(int[] p,int x) {
		if(x==p[x])return x;//부모
		else return p[x]=findSet(p,p[x]);
	}
	
	public static void union(int[] p,int x,int y) {
		x=findSet(p,x);
		y=findSet(p,y);
		if(x>y)p[x]=y;
		else p[y]=x;
	}
	public static boolean find(int[] p,int x,int y) {
		return findSet(p,x)==findSet(p,y);
	}
}