[백준] 1717 집합의 표현(Java) [Union-Find]

문제

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

 

 

알고리즘

Union-Find

 

 

풀이

대표적인 union-find 문제이다.

parent를 얻어오는 함수, parent를 합치는 함수, parent가 동일한지 확인하는 함수를 구현한 후 입력 받는 flag에 따라 parent를 합치거나 출력한다.

 

 

코드

package com.company;

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

public class Test_UnionFind {

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

    public static void main(String args[]) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(bf.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        StringBuilder sb = new StringBuilder();

        parent = new int[N + 1];


        for (int i = 1; i <= N; i++) {
            parent[i] = i;
        }

        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(bf.readLine());
            int flag = Integer.parseInt(st.nextToken());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());

            
            if (flag == 0) { //union 
                unionParent(a, b);
            } else { //find
                if(isSameParent(a,b)) sb.append("YES");
                else sb.append("NO");
                sb.append("\n");
            }
        }

        bw.write(sb.toString());
        bw.flush();
        bw.close();
    }

    //부모 합치기
    static void unionParent(int a, int b) {
        a = getParent(a);
        b = getParent(b);

        //일반적으로 작은 값을 부모로 한다.
        if (a < b) {
            parent[b] = a;
        } else {
            parent[a] = b;
        }
    }

    //부모를 얻어오기
    static int getParent(int x) {
        if (parent[x] == x) return x;
        return parent[x] = getParent(parent[x]);
    }

    //부모가 동일한지 확인
    static boolean isSameParent(int a, int b) {
        return getParent(a) == getParent(b);
    }
}