[자바] 백준 1717번: 집합의 표현

 

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

1717번: 집합의 표현

 

이코테, 자료구조에서도 배웠었던 find-union 알고리즘이다.

오랜만에 짜보니 대충은 생각나도 제대로 구현하기가 좀 힘들었는데

 

이코테에서 배웠던 알고리즘이 조금 더 간단했던것 같아서

그때 배운 그대로 작성 해 봤다.

2022.08.08 - [파이썬 공부/이코테] - 8. 기타 그래프 이론: 서로소 집합 자료구조 union, find

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

public class P1717 {

	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());

		int[] parent = new int[n + 1];
		for (int i = 0; i <= n; i++) {
			parent[i] = i;
		}

		for (int i = 0; i < m; i++) {
			st = new StringTokenizer(br.readLine());
			int a = Integer.parseInt(st.nextToken());
			int b = Integer.parseInt(st.nextToken());
			int c = Integer.parseInt(st.nextToken());
			if (a == 0) {
				union(parent, b, c);
			} else if (a == 1) {
				int parent_b = find(parent, b);
				int parent_c = find(parent, c);
				if (parent_b == parent_c) {
					System.out.println("YES");
				} else {
					System.out.println("NO");
				}
			}
		}
	}

	private static int find(int[] parent, int x) {
		if (parent[x] != x) {
			parent[x] = find(parent, parent[x]);
		}
		return parent[x];
	}

	private static void union(int[] parent, int b, int c) {
		int parent_b = find(parent, b);
		int parent_c = find(parent, c);

		if (parent_b < parent_c) {
			parent[parent_b] = parent_c;
		} else {
			parent[parent_c] = parent_b;
		}
	}

}