[백준 1717] 집합의 표현 (JAVA)

https://www.acmicpc.net/problem/1717

1717번: 집합의 표현

 

 

이 문제는 유니온 파인드를 사용하면 쉽게 해결할 수 있었다!

 

https://brenden.tistory.com/33

[알고리즘] 유니온 파인드 (Union-Find)

 

처음에는 자신의 번호를 부모 번호로 세팅한다.

입력 받은 두 숫자중에서 작은 숫자를 찾아서 부모 번호로 저장한다.

 

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

public class Main {
	static int[] parent;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int n = Integer.parseInt(st.nextToken());
		int m = Integer.parseInt(st.nextToken());

		parent = new int[n + 1]; //부모 집합 번호 배열
		for (int i = 0; i < n + 1; i++)
			parent[i] = i;

		for (int i = 0; i < m; i++) {
			st = new StringTokenizer(br.readLine());
			int x = Integer.parseInt(st.nextToken());
			int a = Integer.parseInt(st.nextToken());
			int b = Integer.parseInt(st.nextToken());

			if (x == 0) {
				unionParent(a, b);
			} else {
				if (isSameParent(a, b)) {
					System.out.println("YES");
				} else
					System.out.println("NO");
			}
		}

	}

	//부모가 같은지 확인!
	static boolean isSameParent(int x, int y) {
		x = find(x);
		y = find(y);
		if (x == y) {
			return true;
		}
		return false;
	}

	//작은 숫자로 부모 합치기
	static void unionParent(int a, int b) {
		a = find(a);
		b = find(b);
		if (a != b) {
			if (a < b)
				parent[b] = a;
			else
				parent[a] = b;
		}
	}

	//부모 찾기
	static int find(int x) {
		if (parent[x] == x)
			return x;
		return parent[x] = find(parent[x]);
	}
}