집합의 표현

알고리즘 구분 : 유니온 파인드

문제

초기에 {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 를 출력해도 된다)

예제 입력 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

문제 풀이

문제에서 대놓고 유니온 파인드를 사용하라고 알려준 유형이다.
유니온 파인드의 기본 틀을 다 구현한 이후에, findParent가 동일한 경우와 아닌 경우에 대한 출력 조건문만 구현하면 되는 간단한 문제다.

소스 코드

#include <bits/stdc++.h>

using namespace std;

#define endl "\n"

int n, m;
int parent[1000001];
int findParent(int parent[], int x);
void unionParent(int parent[], int a, int b);

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    cin >> n >> m;

    for(int i = 0; i < n + 1; i++) {
        parent[i] = i;
    }

    for(int i = 0; i < m; i++) {
        int num, a, b;
        cin >> num >> a >> b;
        if(num == 0) {
            unionParent(parent, a, b);
        }
        else if(num == 1) {
            if(findParent(parent, a) == findParent(parent, b)) {
                cout << "YES" << endl;
            }
            else {
                cout << "NO" << endl;
            }
        }
    }

    return 0;
}

int findParent(int parent[], int x) {
    if(parent[x] != x) {
        return parent[x] = findParent(parent, parent[x]);
    }

    return parent[x];
}

void unionParent(int parent[], int a, int b) {
    int pa = findParent(parent, a);
    int pb = findParent(parent, b);

    if(pa < pb) {
        parent[pa] = pb;
    }
    else {
        parent[pb] = pa;
    }
}

• 문제 출처 : https://www.acmicpc.net/problem/1717
• 해당 풀이는 백준에서 "맞았습니다!!" 판정을 받았습니다.