[1717] 집합의 표현

문제 링크 : https://www.acmicpc.net/problem/1717

1717 - 집합의 표현

본문

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

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

입력

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

출력

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

제한

시간 제한	메모리 제한
2sec	128MB

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

---

풀이

유니온파인드 기본 문제다. disjoint set 문제에 쿼리를 추가한 것. 사실상 분리집합만 만들어주고 쿼리를 실현시키면 된다. 인터랙티브한 문제라서 미리 결과를 계산해두고 저장할 필요도 없다.

기본형 문제라서 이 문제를 토대로 분리 집합을 설명해도 될 것 같다. 따로 포스트를 적으면 참고에 추가할 것이다.

• 참고 알고리즘 : 분리 집합

코드

사용 언어 : C

최종 수정일 : 2023 / 3 / 20

#include <stdio.h>

#define MAX_IDX (int)(1e6 + 1)

int parent[MAX_IDX];
int n;

int find(int x) {
    if (parent[x] == x) {
        return x;
    } else {
        return parent[x] = find(parent[x]);
    }
}
void grouping(int a, int b) {
    int x = find(a), y = find(b);
    if (x != y) {
        parent[y] = parent[b] = x;
    }
    return;
}

int main() {
    int m;
    scanf("%d %d", &n, &m);
    for (int i = 1; i <= n; ++i) {
        parent[i] = i;
    }

    while (m--) {
        int a, b, c;
        scanf("%d %d %d", &a, &b, &c);

        switch (a) {
            case 0: {
                grouping(b, c);
                break;
            }
            case 1: {
                if (find(b) == find(c)) {
                    printf("YES\n");
                } else {
                    printf("NO\n");
                }
                break;
            }
        }
    }

    return 0;
}