[Algorithm]Baekjoon 1717번 :: 집합의 표현 (유니온파인드 기본문제)

Union-Find 알고리즘의 기본예제다.

좀 더 난이도있는 그래프문제를 해결하려고 할 수록, 필수로 알아두는게 좋다고 한다.

 

 

 

#include <iostream>
 
 
using namespace std;
#pragma warning(disable:4996)
 
int parent[1000001];
 
int getParent(int x)
{
    if (parent[x] == x) 
    {
        return x;
    }
        
    return parent[x] = getParent(parent[x]);
}
 
 
void UnionParent(int a, int b)
{
    a = getParent(a);
    b = getParent(b);
 
    if (a > b) parent[a] = b;
    else parent[b] = a;
}
 
void Find(int a, int b)
{
    a = getParent(a);
    b = getParent(b);
 
    if (a == b)
    {
        cout << "YES\n";
    }
    else
    {
        cout << "NO\n";
    }
 
}
 
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
 
    int n = 0;
    int m = 0;
    int s = 0;
    int a = 0;
    int b = 0;
 
    cin >> n >> m;
    
    for (int i = 0; i <= n; i++)
    {
        parent[i] = i; // 각 노드의 부모정보초기화
    }
 
    for (int i = 0; i < m; i++)
    {
        cin >> s >> a >> b; 
 
        if (s == 0)
        {
            UnionParent(a, b);
        }
        else
        {
            Find(a, b);
        }
    }
 
    return 0;
}