Home [1717] 집합의 표현
Post
Cancel

[1717] 집합의 표현

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

1717 - 집합의 표현

본문

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

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

입력

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

출력

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

제한

시간 제한메모리 제한
2sec128MB
  • 1n1000000
  • 1m100000
  • 0a,bn
  • a, b는 정수
  • ab는 같을 수도 있다

풀이

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

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

코드

사용 언어 : C

최종 수정일 : 2023 / 3 / 20

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
#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;
}
This post is licensed under CC BY 4.0 by the author.