[백준 C++] 1717 집합의 표현

문제

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

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

입력

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

출력

1로 시작하는 입력에 대해서 한 줄에 하나씩 YES/NO로 결과를 출력한다. (yes/no 를 출력해도 된다)

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

풀이

Disjoint Set Union 알고리즘을 이해 했다면 풀 수 있다. 다만, 보통의 DSU알고리즘이 단 2개의 집합만을 고려한다면 이문제는 최대 N+1개의 집합을 고려한다는것.
문제를 읽어보면 두번째줄부터 0 이면 Union 과정을 하여, 두 원소 a, b 를 이어주고
1 이면 두 원소 a, b가 같은 집합인지 확인하라고한다.
Union 과정에서 Find 함수가 쓰이고,
같은 집합인지 확인하는 과정은 두 원소의 대표원소(루트원소)가 동일한지를 판별해주면된다.

1. Find 함수
   해당원소의 부모원소를 리턴하되, 해당 원소가 어느 집합에 속해있다면.(부모원소가 설정되있는경우. 부모원소가 본인을 가리키지 않는경우)경로압축을 통해 부모원소를 해당 집합트리의 루트원소로 경로압축을 해준다.(시간단축 핵심)

2. Union 함수
   각 원소의 부모원소를 x, y에 저장한뒤에
   임의로 항상 x원소를 y의 자식으로 추가하도록 코딩하였다.
   이부분에서 기준점을 삼도록 코딩해도된다.
   if(a > b) parent[y] = x else parent[x] = y 등.

3. isUnion 함수
   두원소의 루트원소가 같다면 같은 집합임을 판별해준다.

#define _CRT_SECURE_NO_WARNINGS 
#include <bits/stdc++.h>
int n, m;
int parent[1000001];

int Find(int x) {
    if (parent[x] == x)
        return x;
    return parent[x] = Find(parent[x]); //경로압축
}

void Union(int x, int y) {
    x = Find(x);
    y = Find(y);
    parent[x] = y;
}

bool isUnion(int x, int y) {
    x = Find(x);
    y = Find(y);
    if (x == y)
        return true;
    return false;
}

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

void logic() {
    while (m--) {
        int sign, a, b;
        scanf("%d%d%d", &sign, &a, &b);
        if (sign == 0)
            Union(a, b);
        else {
            if (isUnion(a, b))
                printf("YES\n");
            else
                printf("NO\n");
        }   
    }
}

int main(void) {
    init();
    logic();

    return 0;
}