[C++][백준 1717] 집합의 표현

[문제]

1717번: 집합의 표현 (acmicpc.net)

1717번: 집합의 표현

[풀이 방법]

대표적인 유니온 파인드 문제이다.

최대 가능한 수인 1,000,000을 배열로 만들어두고 해당 배열을 find, merge의 두개의 함수를 이용해서 결합을 시키는 과정을 걸친뒤에 isUnion함수를 이용해서 두개의 값이 연결되어있는지 아닌지 확인하면 된다.

 

*첫번째 함수를 find라고 만들었지만 find라는 함수는 c++에 이미 있는 이름이기 때문에 나중에 헷갈릴수 있다. 나중에 함수 이름을 어떻게 바꿀지 고민해보자.

 

*주의사항 : 출력 코드의 길이가 최대 1,000,000 이기 때문에 endl 을 쓸거면 #define endl "\n 을 통해서 endl의 시간을 단축시켜야 한다.

[코드]

#include <iostream>
#define endl "\n"
using namespace std;

int parent[1000001];

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

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

bool isUnion(int a, int b){
    a = find(a);
    b = find(b);
    if(a == b){
        return true;
    }
    return false;
}

int main(){

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

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

    int n,m;
    cin>>n>>m;

    for(int i = 0;i<m;i++){
        int isFind, a, b;
        cin>>isFind>>a>>b;
        if(isFind == 0){
            merge(a,b);
        }
        else if(isFind == 1){
            if(isUnion(a,b) == 0){
                cout<<"NO"<<endl;
            }
            else{
                cout<<"YES"<<endl;
            }
        }
    }

    return 0;
}