[Algorithm] SWEA 3289 서로소 집합

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWBJKA6qr2oDFAWr 

SW Expert Academy

 

---

 

import java.io.*;
import java.util.*;

public class Solution {
	
	static int[] parents;
	static int n;
	
	private static void make() { // 초기 집합 구성
		parents = new int[n + 1];
		for(int i = 1; i < n+1; i++)	parents[i] = i;
	}
	
    
	private static int find (int a) { // 대표자 탐색
		if (a == parents[a])	return a;
		return parents[a] = find(parents[a]);
	}
	
    
	private static boolean union (int a, int b) { // 합집합 수행
		int aRoot = find(a);
		int bRoot = find(b);
		if (aRoot == bRoot)	return false;
		
		parents[bRoot] = aRoot;
		return true;
	}
	

	public static void main (String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int T = Integer.parseInt(st.nextToken());
		
		for (int t = 1; t <= T; t++) {
			String result = "";
			
			st = new StringTokenizer(br.readLine());
			n = Integer.parseInt(st.nextToken());
			int m = Integer.parseInt(st.nextToken()); // 연산 개수
			
			make();
			
			for (int i = 0; i < m; i++) {
				st = new StringTokenizer(br.readLine());
				int op = Integer.parseInt(st.nextToken()); // 0 : 합집합 수행, 1 : 두 원소가 같은 집합인지 확인
				switch (op) {
					case 0 :
						union(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()));
						break;
					case 1 :
						if (find(Integer.parseInt(st.nextToken())) == find(Integer.parseInt(st.nextToken())))
							result += "1";
						else
							result += "0";
						break;
				}
			}
			System.out.println("#" + t + " " + result);
		}
	}
}