[Baekjooin] 1717번: 집합의 표현 (c++)

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

1717번: 집합의 표현

 

시간초과가 떠서 왜지 싶었는데 입출력이 느려서 아랫줄을 추가해줘야 했다.

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

https://www.acmicpc.net/problem/15552 참고

 

 

합집합 연산이라는 말에 Union Find를 써야겠구나 생각했다.

(0, a, b) 에서 맨앞이 0이면 a가 포함된 집합과 b가 포함된 집합을 묶어주고 (Union)

(1, a, b)에서 맨앞이 1이면 a와 b의 부모를 각각 찾고(Find), 부모가 같으면 같은 집합이므로 "YES", 아니면 "NO"를 출력한다.

 

 

---

코드(c++)

#include <string>
#include <vector>
#include <iostream>
using namespace std;

int parent[1000001] = {0,};

int Find(int x){
    if(x==parent[x]) return x;
    else{
        int p = Find(parent[x]);
        parent[x] = p;
        return p;
    }
}

void Union(int x,int y){
    x = Find(x);
    y = Find(y);
    
    if(x!=y) parent[y] = x;
}

int main(){
    ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    
    int n,m, c,a,b;
    cin >> n >> m;

    for(int i=1;i<=n;i++){ parent[i] = i;}
    while (m--) {
     
        cin >> c >> a >> b;
        if(c == 0){ //합집합 연산
            
            Union(a, b);
            
        } else if(c == 1){
            
            int a_parent = Find(a);
            int b_parent = Find(b);
            
            if(a_parent == b_parent) cout << "YES\n";
            else cout << "NO\n";

        }
    }
    return 0;
}