[백준] 1717번 집합의 표현

1717 집합의 표현

문제

---

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

---

풀이)

Union-Find 방법으로 푸는 문제다.

집합의 부모를 저장하는 parent배열과 각 집합의 사이즈를 저장하는 s배열을 선언해서 이용했다.

코드)

#include <stdio.h>
#include <algorithm>
using namespace std;
 
int n, m;
int parent[1000001];
int s[1000001];
int Find(int a) {
    if (parent[a] == a) return a;
    return parent[a] = Find(parent[a]); // 경로압축
}
void Union(int a, int b) {
    a = Find(a);
    b = Find(b);
    if (a == b) return;//이미 같은 집합이면 안합침
    //집합 큰 곳에다가 합침
    if (s[b] > s[a]) swap(a, b); //큰 곳을 a집합으로
    parent[b] = a;
    s[a] += s[b];
}
int main() {
    scanf("%d %d", &n, &m);
    for (int i = 0; i <= n; i++) {
        parent[i] = i;
        s[i] = 1;
    }
    for (int i = 0; i < m; i++) {
        int cal, a, b;
        scanf("%d %d %d", &cal, &a, &b);
        if (cal == 0) {//집합 a b를 합친다.
            Union(a, b);
        }
        else { //원소 a,b 같은집합?
            a = Find(a);
            b = Find(b);
            if (a == b) printf("YES\n");
            else printf("NO\n");
        }
    }
    return 0;
}