[백준]BOJ #1717: 집합의 표현

작성일 | In

문제 출처: https://www.acmicpc.net/problem/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 를 출력해도 된다)

예제 입력 1

1
2
3
4
5
6
7
8
9
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

예제 출력 1

1
2
3
NO
NO
YES

문제 분석

  1. Disjoint Set 의 구현

문제 풀이( 코드)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
#include <bits/stdc++.h>
#define MAX 1000001
#define INF 2e9
#define foi(n) for(int i=0;i<n;++i)
#define endl '\n'
#define vi vector<int>

using namespace std;

class DisjointSet{
    unordered_map<int, int>parent;
    public:
    void makeSet(vi const &wholeset){
        for(int i:wholeset) parent[i]=i;
    }
    void makeSetwithN(int n){
        for(int i=1;i<=n;i++) parent[i]=i;
    }
    int Find(int target){
        if(parent[target]==target) return target;
        return parent[target]=Find(parent[target]);    //recursion & renew parent[target] in order to reduce duplicated calls
    }
    void Union(int m, int n){
        int x=Find(m);
        int y=Find(n);
        parent[x]=y;
    }
};

DisjointSet d;
int n, m;
void opr(int op, int a, int b){
    if(op==0){
        d.Union(a,b);
    }
    else{
        if(d.Find(a)==d.Find(b)) cout<<"YES\n";
        else cout<<"NO\n";
    }
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);cout.tie(NULL);
    
    cin>>n>>m;
    d.makeSetwithN(n);
    int op, a, b;
    foi(m){
        cin>>op>>a>>b;
        opr(op, a, b);
    }
}

Point

  1. Find 연산을 할 때 단순히 return Find(parent[target]); 을 해도 되지만 동시에 parent[target] 값을 갱신해줌으로써 이후에 중복되는 연산을 줄일 수 있다. 이를 Path Compression, 경로 압축이라고 함.

path-compression

Reference