BOJ 1717 집합의 표현 [Java]

문제

BOJ 1717 집합의 표현

접근방법

• 그래프 이론에서 가장 기본 함수인 find(), union() 학습 유무를 묻는 문제
• 고려할 점이 find()가 재귀함수인데, 할당도 동시에 해줘야 메모리소모 및 시간이 훠얼씬 줄어든다.

구현

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

public class Main {
    static int N, M;
    static int [] Group;

    public static void main(String[] args) throws NumberFormatException, IOException {
        StringTokenizer st;
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        st = new StringTokenizer(br.readLine(), " ");
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

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

        int Q, a, b;
        for(int i = 1 ; i <= M ;i++) {
            st = new StringTokenizer(br.readLine(), " ");
            Q = Integer.parseInt(st.nextToken());
            a = Integer.parseInt(st.nextToken());
            b = Integer.parseInt(st.nextToken());

            if(Q == 0) {
                union (a, b);
            }

            if (Q == 1) {
                if(find(a) == find(b)) {
                    System.out.println("YES");
                } else {
                    System.out.println("NO");
                }
            }
        }
    }

    static void union(int a, int b) {
        int aGroup = find(a);
        int bGroup = find(b);

        Group[aGroup] = bGroup;
    }

    static int find(int i) {
        if (Group[i] == i) return i;

        else return Group[i] = find(Group[i]);
    }
}

제출