[BOJ] 1717번 : 집합의 표현

문제 링크 : 백준 1717번

[문제 접근]

전형적인 Union-Find문제이다.
집합인가 아닌가만 따지므로 level부분은 빼도 될 것 같다.

⭐ ios_base::sync_with_stdio(false);, cin.tie(0);를 써줘야 시간초과가 발생하지 않는다.

[소스 코드]

#include <iostream>
#include <algorithm>

using namespace std;
int n,m;
int parent[1000001];
int level[1000001];

int Find(int node) {
    if(node == parent[node]) return node;
    return parent[node] = Find(parent[node]);
}

void Union(int a, int b) {
    a = Find(a);
    b = Find(b);

    if(a!=b) {
        if(level[a]<level[b]) {
            parent[a] = b;
        }
        else {
            parent[b] = a;
        }

        if(level[a] == level[b]) level[a]++;
    }
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> m;
    for(int i=1 ; i<=1000000 ; i++) {
        parent[i] = i;
        level[i] = 0;
    }
    
    for(int i=0 ; i<m ; i++) {
        int check, a, b;
        cin >> check >> a >> b;
        if(check == 0) {
            Union(a, b);
        }
        else {
            int temp1 = Find(a);
            int temp2 = Find(b);
            if(temp1 == temp2) cout << "YES\n";
            else cout << "NO\n";
        }
    }

    return 0;
}