[백준] 분리집합(유니온-파인드)

백준 문제 풀이

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

1717번: 집합의 표현

분리 집합 알고리즘

-교집합이 존재하지 않는 두개 이상의 집합을 뜻한다.

-같은 집합에 속한 원소들을 O(1)의 시간 복잡도로 확인하는 방법으로 사용된다.

-따라서 같은 집합에 속한 부모 값을 기준으로 두 집합을 Union(합)-Find(찾기)를 진행한다.

-대표값(부모 노드)를 찾아 이용한다.

 

Union 연산

-합집합 연산으로 a, b 두 개의 집합을 합치기 위해 각 집합의 부모 노드를 찾고 a의 부모노드의 부모를 b의 부모로 설정하여 연결한다.

-ex) 집합 a = {1, 2, 3} 대표값 1, 집합 b = {4, 5, 6} 대표값 4면 Union(a, b)를 진행한 집합 ab는 ab = {4, 5, 6, 1, 2 ,3}인데 이때 a의 대표값 1이 b의 대표값 4 아래 연결되어 트리 형태를 이룬다고 생각하자.

 

Find 연산

-해당 원소가 속한 집합을 찾고, 이 집합에서 부모 노드를 찾아 반환한다.

 

풀이법

#include<iostream>
#include<vector>
#include<algorithm>

#define FastIO ios::sync_with_stdio(false); std::cin.tie(NULL); std::cout.tie(NULL);

using namespace std;

vector<int> parent; //자신의 부모의 번호를 저장

int Find(int num)
{
    if(parent[num] == num)
    {
        return num;
    }
    parent[num] = Find(parent[num]);
    return parent[num];
}

void Union(int a, int b)
{
    int parentA = Find(a);
    int parentB = Find(b);
    if(parentA == parentB)
    {
        return;
    }
    parent[parentB] = parentA;
}

int main(void)
{
    FastIO;
    
    int n = 0, m = 0;
    std::cin >> n >> m;
    
    //초기 원소들의 대표값은 본인이니 본인으로 초기화
    for(int i = 0; i <= n; i++)
    {
        parent.push_back(i);
    }
    
    int cmd = 0, a = 0, b = 0; //명령어, 두 원소 a, b
    for(int  i = 0; i < m; i++)
    {
        std::cin >> cmd >> a >> b;
        if(cmd == 0)
        {
            Union(a, b);
        }
        else
        {
            if(Find(a) == Find(b))
            {
                std::cout << "YES" << "\n";
            }
            else
            {
                std::cout << "NO" << "\n";
            }
        }
    }
    return 0;
}