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

문제

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

백준 1717

 

문제 내용

두 원소가 같은 집합에 있는지 아닌지를 출력하면 되는 문제이다.

합집합 연산은 0 a b 형태로 주어지고, 1 a b는 a와 b가 같은 집합인지를 출력하라는 명령이다.

 

문제 풀이

유니온 파인드를 구현할 줄 알면 해결할 수 있다.

 

코드

#include <iostream>
#include <vector>
using namespace std;

vector<int> parent; // 값이 음수면 그 노드가 root라는 뜻, 양수는 자신의 부모를 나타냄

int findParent(int node) {
    if (parent[node] < 0) {
        return node; // 루트 정점
    }

    return parent[node] = findParent(parent[node]); // 그래프 압축하여 루트 정점 찾기
}

void unionInput(int x, int y) {
    int nodeX = findParent(x);
    int nodeY = findParent(y);

    if (nodeX == nodeY) { // 이미 같은 집합
        return;
    }

    if (parent[nodeX] < parent[nodeY]) { // nodeX 쪽 집합이 더 큰 경우
        parent[nodeX] += parent[nodeY];
        parent[nodeY] = nodeX;
    } else {
        parent[nodeY] += parent[nodeX];
        parent[nodeX] = nodeY;
    }
    // 위와 같이 갱신을 하면, find를 한 번 거쳐야 루트 정점이 갱신된다.
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int n, m;
    cin >> n >> m;
    parent.assign(n + 1, -1); // 1~n

    int cmd, a, b;
    while (m--) {
        cin >> cmd >> a >> b;

        if (cmd == 0) { // union 연산
            unionInput(a, b);
        } else { // 같은 집합에 포함되어있는지
            if (findParent(a) == findParent(b)) // parent[a]가 아니라 find연산을 해야한다.
                cout << "YES\n";
            else
                cout << "NO\n";
        }
    }

    return 0;
}