백준) 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 를 출력해도 된다)

예제 입력 

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

1. 접근

파티션질이 필요한 문제. 두 원소가 같은 집합에 있는지만 판별해주면 되므로 disjoint-set을 사용하자.

2. 풀이

원소들은 0 이상, 백만 이하의 정수이므로 백만칸 짜리 인트형 배열로 부모들을 저장해주자.

이어서 find() 연산과 union() 연산을 구현해주고

연산이 1이면 a와 b가 속한 집합의 대표가 find()로 같은지 확인하고, 0이면 union(a, b)를 수행한다.

3. 코드 

#include <stdio.h>
using namespace std;
 
int n, m, i, a, b, c;
int parent[1000001];
 
int find(int x) {
    if (x == parent[x])
        return x;
    else
        return parent[x] = find(parent[x]);
}
 
void unite(int x, int y) {
    x = find(x);
    y = find(y);
    parent[x] = y;
}
 
int main() {
    scanf("%d %d", &n, &m);
    for (i = 0; i <= n; ++i)
        parent[i] = i;
 
    while (m--) {
        scanf("%d %d %d", &c, &a, &b);
 
        if (!c)
            unite(a, b);
        else
            if (find(a) == find(b))
                puts("YES");
            else
                puts("NO");
    }
    return 0;
}