서로소 집합 [Swea 3289][Java]

[광고 누르면 오늘의 행운 상승!!]

[광고 누르면 오늘의 행운 상승!!]

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWBJKA6qr2oDFAWr&categoryId=AWBJKA6qr2oDFAWr&categoryType=CODE&&&

SW Expert Academy

문제의 저작권은 Sw Expert Academy에 있습니다.

unionFind를 사용하여 같은 집합인지 확인한 후 나누었다.

package Study;

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

public class 서로소 {

	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; //x가 더 크면 x의 부모는 y
		else    p[y] = x; //y가 더 크면 y의 부모는 x
	}
	public static boolean find(int[] p, int x, int y) {
		return (findSet(p,x) == findSet(p,y));
	}
	public static void main(String[] args) throws Exception {
		System.setIn(new FileInputStream("test.txt"));
		Scanner sc = new Scanner(System.in);
		int T = sc.nextInt();
		for (int tc = 1; tc <= T; tc++) {
			int n = sc.nextInt();
			int m = sc.nextInt();
			
			int[] arr= new int[n+1];
			for (int i = 1; i <= n; i++) {
				arr[i] = i;
			}
			System.out.print("#" + tc + " ");
			for (int i = 0; i < m; i++) {
				int kind = sc.nextInt();
				int a = sc.nextInt();
				int b = sc.nextInt();
				
				if(kind == 1) {//a와 b가 서로 같은 집합인지 확인
					if(find(arr, a,b)) System.out.print(1);
					else 			   System.out.print(0);	
				}else {//합집합
					union(arr, a , b);
				}
			}
			System.out.println();
		}
		
	}

}