1717번: 집합의 표현

1717번: 집합의 표현

사용 언어: C++

문제 요약

초기에 0, 1, 2, ..., n의 원소 각각이 자기 자신만 담은 n+1개의 서로 집합으 ㄹ이룬다. 두 연산을 m번 처리한다.

1. 합집합 연산 : o a b -> a 가 속한 집합과 b가 속한 집합을 합친다.

2. 동일 집합 질의: 1 a b -> a와 b가 ㅈ같은 집합에 속하면 YES, 아니면 No를 출력. 제한은 n <= 1,000,000, m <= 100,000이며, 0<= a,b <= n이다.

풀이

합집합을 하고 해당 두 수가 같은 집합에 있는지 찾는 최적의 방식은 유니온 파인드다.

유니온 파인드의 핵심 연산은 두 가지다.

1. find(x)

- 원소 x가 속한 집합의 대표(root)를 찾는다

int find_parent(vector<int>& parent, int x)
{
    if(parent[x] == x) return x;
    
    return parent[x] = find_parent(parent, parent[x]);
}

 

2. union(a, b)

- a, b의 두 대표를 찾아 서로 다르면 한 쪽을 다른 쪽의 부모로 붙인다.

void union_sets(vector<int>& parent, int x, int y)
{
    int rootX = find_parent(parent, x);
    int rootY = find_parent(parent, y);
    
    if(rootX != rootY) parent[rootY] = rootX;
}

 

답

#include <iostream>
#include <vector>

using namespace std;

int find_parent(vector<int>& parent, int x)
{
    if(parent[x] == x) return x;
    
    return parent[x] = find_parent(parent, parent[x]);
}

void union_sets(vector<int>& parent, int x, int y)
{
    int rootX = find_parent(parent, x);
    int rootY = find_parent(parent, y);
    
    if(rootX != rootY)
    {
        parent[rootY] = rootX;
    }
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    int n, m;
    cin >> n >> m;
    
    vector<int> parent(n+1);
    for(int i=0; i<=n; i++)
    {
        parent[i] = i;
    }
    
    for(int i=0; i<m; i++)
    {
        int op, a, b;
        cin >> op >> a >> b;
        
        if(op == 0)
        {
            union_sets(parent, a, b);
        }
        else
        {
            if(find_parent(parent, a) == find_parent(parent, b))
            {
                cout << "YES\n";
            }
            else
            {
                cout << "NO\n";
            }
        }
    }

    return 0;
}