[BOJ / C++] 1717 집합의 표현 : Union-Find

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

문제풀이

Union-Find의 기본틀을 사용해서 풀 수 있는 문제였다.

하지만....입출력 속도 향상을 안해줘서 시간초과로 계속 헤맸다 😵

✨✨✨✨✨✨✨✨기억해!@!@!

ios_base::sync_with_stdio(false); 
cout.tie(NULL); 
cin.tie(NULL);

• unf[i] : i의 루트노드
• Find(v) : v의 루트노드를 찾아냄
• Union(a, b) : a와 b의 루트노드를 찾은 후, 다르면 (다른 트리에 속하면) 한 쪽을 다른 쪽 아래에 연결해준다.

코드

#include <iostream>
using namespace std;
#define MAX 1000000+1
int n,m;
int unf[MAX]; //unf[i] : i의 root

//부모 노드 찾기!
int Find(int v){
    if(unf[v]==v) return v; //자기 자신이 최상위
    else return unf[v]=Find(unf[v]); //최상위 노드를 찾으면서 동시에 시간 효율성 향상
}

void Union(int a, int b){
    a=Find(a);
    b=Find(b);
    //부모노드가 다르면 한쪽에 연결
    if(a!=b) unf[a]=b;
}
int op,a,b;
int main(){
    ios_base::sync_with_stdio(false); cout.tie(NULL); cin.tie(NULL);
    cin>>n>>m;
    for(int i=1;i<=n;i++) unf[i]=i;
    for(int i=0;i<m;i++){
        cin>>op>>a>>b;
        if(op==0){
            Union(a,b);
        }
        else if(op==1){
            if(Find(a)==Find(b)) cout<<"YES\n";
            else cout<<"NO\n";
        }
    }
    return 0;
}