백준 1717 - 집합의 표현

백준 1717 문제 바로가기

풀이

Union-Find(;Disjoint-Set) 알고리즘을 사용하여 해결한다.

Union-Find는 그래프에 여러 노드가 존재할 때, 임의의 두 노드가 서로 같은 그래프에 속하는지 판별하는 알고리즘이다.

• find(u) : 정점 u가 어떤 집합에 포함되어 있는지 찾는 연산
• union(u, v) : 정점 u, v가 포함되어 있는 집합을 하나로 합치는 연산

---

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

0 a b 형태로 입력을 받았을 때 정점 a를 정점 b가 속한 집합에 합치는 형태로 구현하였으며, 위 예시를 사용한 결과는 아래와 같다.

소스 코드

merge 함수가 union 역할을 수행한다. (C++에서 union이 예약어이므로 함수 이름을 merge로 명명함)

#include <iostream>
using namespace std;


int parent[1000001];
int find(int u) {
    if (parent[u] == u) {
        return u;
    }
    return parent[u] = find(parent[u]);
}
void merge(int u, int v) {
    u = find(u);
    v = find(v);
    if (u == v) return;
    parent[u] = v;
}

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

    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= n; ++i) {
        parent[i] = i;
    }

    for (int i = 0; i < m; ++i) {
        int id, a, b;
        cin >> id >> a >> b;
        if (id == 0) {
            merge(a, b);
        }
        else {
            if (find(a) == find(b)) cout << "YES\n";
            else cout << "NO\n";
        }
    }

    return 0;
}