[백준 1717번] 집합의 표현 :: 늦깎이 IT

[백준 1717번] 집합의 표현 URL

기본적인 Union-Find 문제이므로 이전 포스팅 글을 참고하시기 바랍니다.

2019/03/25 - [알고리즘 이론] - [알고리즘] 유니온 파인드 (Union-Find) :: 늦깎이 IT

[소스 코드]

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.StringTokenizer;
 
public class Main {
 
    static int N, M;
 
    static int[] dirX = new int[] { 0, 0, 1, -1 };
    static int[] dirY = new int[] { 1, -1, 0, 0 };
 
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;
 
    public static void main(String[] args) throws IOException {
 
        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
 
        int[] 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 command = Integer.parseInt(st.nextToken());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            if (command == 0)
                union(parent, a, b);
            else {
                if (find(parent, a, b))
                    System.out.println("YES");
                else
                    System.out.println("NO");
            }
        }
    }
 
    public static int getParent(int[] parent, int node) {
 
        if (parent[node] == node)
            return node;
        else
            return parent[node] = getParent(parent, parent[node]);
    }
 
    public static boolean find(int[] parent, int a, int b) {
 
        int parent1 = getParent(parent, a);
        int parent2 = getParent(parent, b);
 
        if (parent1 == parent2)
            return true;
        else
            return false;
    }
 
    public static void union(int[] parent, int a, int b) {
 
        int parent1 = getParent(parent, a);
        int parent2 = getParent(parent, b);
 
        if (parent1 <= parent2)
            parent[parent2] = parent1;
        else
            parent[parent1] = parent2;
        
    }
 
}