백준 1717번. 집합의 표현(c++) / 유니온파인드

유니온파인드를 사용하는 대표적 문제이다.

문제는....cin, cout이 진짜 느리다는 것을 실감한 문제^^

cin, cout을 쓰니까 맞왜틀이어서 질문 검색란을 찾아보니 똑같은 문제에 시달리시는 분들이 계셔서 ㅋㅋㅋ

ios::sync_with_stdio(0); cin.tie(0); 써서 해결했다.

 

// 집합의 표현(1717번)
#include <iostream>
#include <vector>
 
using namespace std;
 
int n, m, a, b, c;
int connect[1000002] = {0, };
 
int find(int n){
    if(connect[n]==n){
        return n;
    }
 
    return connect[n] = find(connect[n]);
}
 
int main()
{
    ios::sync_with_stdio(0); cin.tie(0);
    cin>>n>>m;
    for(int i=0; i<=n; i++){
        connect[i] = i;
    }
 
    for(int i=0; i<m; i++){
        cin>>a>>b>>c;
        int n = find(b);
        int m = find(c);
        if(a==0){
            if(n!=m){
                connect[n] = m;
            }
        }else{
            if(n==m){
                cout<<"YES"<<"\n";
            }else{
                cout<<"NO"<<"\n";
            }
        }
    }
 
    return 0;
}