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

1717번 : 집합의 표현

---

문제 )

 

 

입력 :

 

 

 

출력 :

 

 

제한 :

 

 

 

 

 

 

풀이)

 

#include <iostream>
 
using namespace std;
 
// x의 부모 노드를 재귀를 이용해서 찾는다
int get_parent(int *parent, int x)
{
    if (parent[x] == x) return x;
    return parent[x] = get_parent(parent, parent[x]);
}
 
// 두 그룹의 부모를 하나로 맞춰준다 (작은 수로)
void union_parent(int *parent, int a, int b)
{
    a = get_parent(parent, a);
    b = get_parent(parent, b);
    if (a < b) parent[b] = a;
    else parent[b] = a;
}
 
int main()
{
    // 많은 수의 입출력으로 인해 cin의 속도를 높여야함.
    cin.tie(0);
    cin.sync_with_stdio(false);
    ios_base::sync_with_stdio(false);
 
    int n, m;
    cin >> n >> m;
 
    // 자기 자신을 부모 노드로 설정
    int parent[1000001];
    for (int i = 1; i < n + 1; i++) parent[i] = i;
 
    for (int i = 0; i < m; i++)
    {
        int flag, a, b;
        cin >> flag >> a >> b;
 
        // 합집합 -> 같은 그룹 만들기
        if (!flag)
        {
            union_parent(parent, a, b);
        }
        else
        {
            // 부모 노드가 같다면 같은 집합이므로 
            if (get_parent(parent, a) == get_parent(parent, b))
            {
                cout << "YES\n";
            }
            else
            {
                cout << "NO\n";
            }
        }
    }
 
    return 0;
}

 

---

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

1717번: 집합의 표현