백준 - 1717, 집합의 표현

집합의 표현 성공스페셜 저지

 

시간 제한메모리 제한제출정답맞힌 사람정답 비율

2 초

128 MB

117694

38274

23382

28.663%

문제

초기에 n+1$n+1$개의 집합 {0},{1},{2},…,{n}$\{0\}, \{1\}, \{2\}, \dots , \{n\}$이 있다. 여기에 합집합 연산과, 두 원소가 같은 집합에 포함되어 있는지를 확인하는 연산을 수행하려고 한다.

집합을 표현하는 프로그램을 작성하시오.

입력

첫째 줄에 n$n$, m$m$이 주어진다. m$m$은 입력으로 주어지는 연산의 개수이다. 다음 m$m$개의 줄에는 각각의 연산이 주어진다. 합집합은 0$0$ a$a$ b$b$의 형태로 입력이 주어진다. 이는 a$a$가 포함되어 있는 집합과, b$b$가 포함되어 있는 집합을 합친다는 의미이다. 두 원소가 같은 집합에 포함되어 있는지를 확인하는 연산은 1$1$ a$a$ b$b$의 형태로 입력이 주어진다. 이는 a$a$와 b$b$가 같은 집합에 포함되어 있는지를 확인하는 연산이다.

출력

1로 시작하는 입력에 대해서 a$a$와 b$b$가 같은 집합에 포함되어 있으면 "YES" 또는 "yes"를, 그렇지 않다면 "NO" 또는 "no"를 한 줄에 하나씩 출력한다.

제한

•  1≤n≤1000000$1 ≤ n ≤ 1\,000\,000$ 
•  1≤m≤100000$1 ≤ m ≤ 100\,000$ 
•  0≤a,b≤n$0 ≤ a, b ≤ n$ 
•  a$a$, b$b$는 정수
•  a$a$와 b$b$는 같을 수도 있다.

예제 입력 1 복사

7 8
0 1 3
1 1 7
0 7 6
1 7 1
0 3 7
0 4 2
0 1 1
1 1 1

예제 출력 1 복사

NO
NO
YES

 

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

public class baekjun_1717 {
    static int[] node;

    public static void main(String[] args) throws Exception {
        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());
        node = new int[N+1];

        for (int i = 0; i <= N; i++) {
            node[i] = i;  // 자기 자신을 부모로 초기화
        }

        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            int con = Integer.parseInt(st.nextToken());
            int left = Integer.parseInt(st.nextToken());
            int right = Integer.parseInt(st.nextToken());

            if (con == 0) {  
                union(left, right);  // 두 집합 합치기
            } else if (con == 1) {  
                if (find(left) == find(right)) {
                    System.out.println("YES");
                } else {
                    System.out.println("NO");
                }
            }
        }
    }

    static void union(int left, int right) {
        int rootL = find(left);
        int rootR = find(right);
        
        if (rootL != rootR) {
            if (rootL < rootR) {
                node[rootR] = rootL;
            } else {
                node[rootL] = rootR;
            }
        }
    }

    static int find(int num) {
        if (num == node[num]) {
            return num;
        }
        return node[num] = find(node[num]);  // 경로 압축 적용
    }
}