[백준] 1717번 : 집합의 표현

문제

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

1717번: 집합의 표현

 

주안점

n(1 ≤ n ≤ 1,000,000), m(1 ≤ m ≤ 100,000)

n과 m의 범위가 커 유니온 파인드를 사용하지 않는다면 시간초과가 나온다.

 

구조

유니온 파인드를 이용한 기본적인 구조

 

 

코드

#include<bits/stdc++.h>
using namespace std;

int n,m,t,a,b;
int p[1000001];

int finnd(int n){
    if(p[n]<0) return n;
    p[n] = finnd(p[n]);
    return p[n];
}

void merge(int a, int b){
    a = finnd(a);
    b = finnd(b);
    if(a==b) return;
    p[b] = a;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    cin>>n>>m;
    fill(p, p+n+1, -1);
    for(int i=0; i<m; i++){
        cin>>t>>a>>b;
        if(t) {
            cout<<(finnd(a)==finnd(b) ? "YES" : "NO")<<"\n";
        }
        else merge(a,b);
    }
}