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

문제링크 : https://www.acmicpc.net/problem/1717

1717번: 집합의 표현

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int MAX = 987654321;

int N, M;
int parent[1000001];

int find_root(int x) //부모찾기
{
    if(x == parent[x]) return x;
    return parent[x] = find_root(parent[x]);
}

bool check(int a, int b) //이어졌는가?
{
    a=find_root(a);
    b=find_root(b);
    if(a==b) return 1;
    return 0;
}

void Union(int a, int b) //병합
{
    a=find_root(a);
    b=find_root(b);
    parent[b]=a;
}


int main()
{
    ios_base::sync_with_stdio(0); 
	cin.tie(0);
    
    cin >> N >> M;

    for(int i=1; i<=N; i++) parent[i]=i;
    for(int i=0; i<M; i++)
    {
        int o, a, b;
        cin >> o >> a >> b;
        if(!o) Union(a, b);
        else 
        {
            if(check(a, b)) cout << "YES" << "\n"; //이어짐
            else cout << "NO" << "\n"; //아님
        }
    }
}

 

크게 어려울 것 없는 분리집합문제이다.

분리집합에 대해 알고 있다면 실버상위문제보다도 쉽게 풀 수 있다.

 

큰 틀은 똑같고, 입력으로 받는 부분에 대해서 병합을 진행할 것인지 병합여부 체크를 진행할 것인지만 나눠져있다.