[백준 1717] 집합의 표현

[백준 1717] 집합의 표현

문제 링크

#include <stdio.h>
#include <iostream>
using namespace std;
int n, m;
int parent[1000001];

int find(int x){
    if(parent[x] == x) return x;
    return parent[x] = find(parent[x]);
}

void merge(int a, int b){
    a = find(a);
    b = find(b);

    if(a == b) return;

    parent[b] = a;
}

void input(){

    scanf("%d %d", &n, &m);

    for(int i=1; i<=n; i++){
        parent[i] = i;
    }

    for(int i=1; i<=m; i++){
        int order;
        scanf("%d", &order);
        if(order){
            int a, b;
            scanf("%d %d", &a, &b);
            a = find(a);
            b = find(b);
            if(a == b) printf("YES\n");
            else printf("NO\n");
        }else{
            int a, b;
            scanf("%d %d", &a, &b);
            merge(a, b);
            
        }
    }
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);

    input();
    // solve();
    return 0;
}

• 기본적인 union-find 문제
• scanf와 printf, ios::sync_with_stdio(false); cin.tie(0);를 해 주어야 시간 초과가 안 난다.