[BOJ/백준] 1717 : 집합의 표현 (C++)

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

BOJ 1717

문제 해석

• 이 문제에서는 초기 상태에서는 독립적인 집합을 이루고 있다가 입력으로 합집합 연산으로 두 집합을 병합을 한다. 또한 두 원소가 같은 집합에 포함되어있는지 확인하는 연산 또한 필요하다. 즉, 전형적인 유니온 파인드 문제임을 알 수 있다.

유니온 파인드란?

풀이

• 유니온 파인드 알고리즘에 대해 알고있다면, 그대로 사용만하면 풀리는 문제이다.

코드

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

static vector<int> parent;
void unionfunc(int a, int b); //union 연산 함수
int find(int a); // 어느 집합에 속하는지 확인하는 함수(대표 노드 반환)
bool checkSame(int a, int b);//두 집합이 같은지 확인하는 함수

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

    int N, M;
    cin>>N>>M;
    parent.resize(N+1);

    for(int i=0; i<=N; i++){
        parent[i]=i; // 각 노드의 대표 노드는 자기 자신으로 초기화
    }
    for(int i=0; i<M; i++){
        int question, a, b;
        cin>>question>>a>>b;

        if(question==0){
            unionfunc(a, b);
        }
        else{
            if(checkSame(a,b)){
                cout<<"YES"<<"\n";
            }
            else{
                cout<<"NO"<<"\n";
            }
        }
    }
}

void unionfunc(int a, int b){
    a=find(a);
    b=find(b);

    if(a!=b){
        parent[b]=a;
    }
}

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

bool checkSame(int a, int b){
    a=find(a);
    b=find(b);

    if(a==b){ //두 원소의 대표 노드가 같다면
        return true;//같은 집합에 속함
    }
    return false;//그렇지 않음
}