8주차(최소신장트리) - [C++]백준1717 집합의 표현

05 May 2022 in Study on Algorithm

백준1717 집합의 표현 링크

문제

예제 입력

---

코드

#include<iostream>
using namespace std;
int n, m;
int arr[1000001];

// 원소가 속한 집합 찾기
int find(int x) {
    //if (arr[x] != x) return find(arr[x]); // 경로압축X
    //return x;
    if (arr[x] != x) arr[x] = find(arr[x]); // 경로압축 = 찾을때 정보를 갱신함
    return arr[x];
}

// 두 원소 집합 합치기
void Union(int a, int b) {
    a = find(a);
    b = find(b);
    // 집합을 대표하는 숫자만 일단 보냄
    if (a < b) arr[b] = a;
    else arr[a] = b;
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); //cin 실행속도 향상

    int n, m;
    cin >> n >> m;

    for (int i = 1; i <= n; i++) arr[i] = i;

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

설명

이 문제는 서로소 집합의 개념을 구현하는 것입니다. 먼저 {1}{2}...{n}의 집합들을 배열로 표현하고 횟수만큼 1(확인)인 같은 집합에 속하는지 확인과 0(합치기)으로 같은 집합으로 합치기를 합니다. 이때, 경로 압축을 하는데 집합이 속하는 것을 체인같은 형식으로 표현하는데 그것이 너무 오래 걸리기 때문에 체인을 줄여서 시간초과를 피할 수 있습니다.

---

결과