[백준 1717번] 집합의 표현

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

집합의 표현 성공스페셜 저지

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
2 초	128 MB	11612	3722	2467	30.487%

문제

초기에 {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 

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 

NO
NO
YES

 

서로소 집합, union-find 기본 문제이다. union-find를 공부하면서 기본 알고리즘에서 더 최적화된 알고리즘이 있는 것을 배웠다. 메모메모!

#include<iostream>
#include<algorithm>
 
using namespace std;
 
int parent[1000001], rank_cnt[1000001];
int n,m,a,b,c;
 
int find(int);
void union_(int,int);
 
int main(){
 
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    cin >> n >> m;
 
    for(int i=1;i<=n;i++) parent[i] = i;
 
    for(int i=0;i<m;i++){
        cin >> a >> b >> c;
 
        if(a){
            if(find(b) == find(c)) cout << "YES\n";
            else cout << "NO\n";
 
        }
        else union_(b,c);
    }
 
    return 0;
}
 
int find(int u){
    if(u == parent[u]) return u;
    return parent[u] = find(parent[u]);
}
 
void union_(int u, int v){
    u = find(u); v = find(v);
 
    if(u == v) return;
    if (rank_cnt[u] > rank_cnt[v]) swap(u,v);
    parent[u] = v;
    if(rank_cnt[u] == rank_cnt[v]) rank_cnt[v]++;
 
    parent[u] = v;
}