백준 1717 집합의 표현 (Java)

1. 문제 링크

1717번: 집합의 표현

 

2. 문제 및 입출력예제

 

3. 문제 풀이

makeSet으로 서로소 집합을 만들고,

입력 받은 명령어가 0인 경우 union으로 합집합을 만들고,

그 외 명령어이 경우 findSet을 이용해 두 집합이 부모가 같은지 확인한다.

 

4. 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;

public class Main {

	static int[] set;
	static int N, M;

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		String[] str = in.readLine().split(" ");
		N = Integer.parseInt(str[0]);
		M = Integer.parseInt(str[1]);

		makeSet();

		for (int i = 0; i < M; i++) {
			str = in.readLine().split(" ");
			int order = Integer.parseInt(str[0]);
			int a = Integer.parseInt(str[1]);
			int b = Integer.parseInt(str[2]);
			if (order == 0) {
				union(a, b);
			} else {
				if (findSet(a) == findSet(b)) {
					sb.append("YES").append("\n");
				} else {
					sb.append("NO").append("\n");
				}
			}
		}
		System.out.println(sb);
	}

	private static void makeSet() {
		set = new int[N + 1];
		for (int i = 0; i <= N; i++) {
			set[i] = i;
		}
	}

	public static int findSet(int a) {
		if (set[a] == a) {
			return a;
		}
		return set[a] = findSet(set[a]);
	}
    
	private static boolean union(int a, int b) {
		int aRoot = findSet(a);
		int bRoot = findSet(b);
		if (aRoot == bRoot) {
			return false;
		}
		set[bRoot] = aRoot;
		return true;
	}
}