백준 1717번 - 집합의 표현

문제

초기에 {0}, {1}, {2}, ... {n} 이 각각 n+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

예시 출력

NO
NO
YES

아이디어

대놓고 유니온 파인드

알고리즘

유니온 파인드

소스코드

#include <bits/stdc++.h>

using namespace std;

int N, M;
int parent[1000010];
int order[100010][3];

int find(int x) {
    if (parent[x] == x)
        return x;
    return parent[x] = find(parent[x]);
}

void merge(int x, int y) {
    int px = find(x);
    int py = find(y);
    if (x > y) 
        parent[px] = py;
    else if (x < y)
        parent[py] = px;
}

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

int main() {
    int k, a, b;

    cin >> N >> M;
    for (int i = 0; i <= N; i++) {
        parent[i] = i;
    }

    for (int i = 0; i < M; i++) {
        cin >> order[i][0] >> order[i][1] >> order[i][2];
    }

    for (int i = 0; i < M; i++) {
        if (order[i][0] == 0) {
            //집합을 합친다.
            merge(order[i][1], order[i][2]);
        }
        if (order[i][0] == 1) {
            //포함확인
            if (isUnion(order[i][1], order[i][2])) {
                cout << "YES\n";
            }
            else {
                cout << "NO\n";
            }
        }
    }

    return 0;
}

알아 가야할것

• 입력부를 먼저 저장하고 처리를 해야한다. 안그러면 시간 초과 나더라..
• 뼈대코드 다시 숙지하자

---