백준 1717번 : 집합의 표현 java

이 문제는 분리 집합을 이용하여 해결하는 문제입니다.

분리 집합이란 union-find 함수를 이용하여 자신과 연결되어 있는 정점인지 확인하여 연결되어 있지 않다면 연결하는
알고리즘입니다.

이 문제에서는 0이 처음 입력으로 주어졌을 경우 뒤의 두 정점을 이어주고 1이 입력으로 들어올 경우 두 정점이 연결되어 있는지를 확인하여 YES나 NO를 출력하면 됩니다.

코드를 바로 보여드리겠습니다.

---

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

public class Main {
    static int[] parent;

    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuffer sb = new StringBuffer();
        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 = 1; i<=N; i++)
            parent[i] = i;

        while(M-->0){
            st = new StringTokenizer(br.readLine());

            int type = Integer.parseInt(st.nextToken());
            int A = Integer.parseInt(st.nextToken());
            int B = Integer.parseInt(st.nextToken());

            if(type == 0)
                union(A, B);

            else if (type == 1){
                int parentA = find(A);
                int parentB = find(B);

                if(parentA == parentB)
                    sb.append("YES").append("\n");
                else
                    sb.append("NO").append("\n");
            }
        }

        System.out.print(sb);
    }

    static int find(int idx){
        if(parent[idx] == idx)
            return idx;
        else
            return find(parent[idx]);
    }
    static void union(int idx1, int idx2){
        int parent1 = find(idx1);
        int parent2 = find(idx2);

        if(parent1 != parent2)
            parent[parent2] = parent1;
    }
}