백준 1717 집합의 표현 c++ (유니온파인드)

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

1717번: 집합의 표현

문제

초기에 {0}, {1}, {2}, ... {n} 이 각각 n+1개의 집합을 이루고 있다. 여기에 합집합 연산과, 두 원소가 같은 집합에 포함되어 있는지를 확인하는 연산을 수행하려고 한다.

집합을 표현하는 프로그램을 작성하시오.

입력

첫째 줄에 n(1 ≤ n ≤ 1,000,000), m(1 ≤ m ≤ 100,000)이 주어진다. m은 입력으로 주어지는 연산의 개수이다. 다음 m개의 줄에는 각각의 연산이 주어진다. 합집합은 0 a b의 형태로 입력이 주어진다. 이는 a가 포함되어 있는 집합과, b가 포함되어 있는 집합을 합친다는 의미이다. 두 원소가 같은 집합에 포함되어 있는지를 확인하는 연산은 1 a b의 형태로 입력이 주어진다. 이는 a와 b가 같은 집합에 포함되어 있는지를 확인하는 연산이다. a와 b는 n 이하의 자연수 또는 0이며 같을 수도 있다.

출력

1로 시작하는 입력에 대해서 한 줄에 하나씩 YES/NO로 결과를 출력한다. (yes/no 를 출력해도 된다)

알고리즘 분류

• 자료 구조
• 분리 집합

풀이

최소 스패닝 트리를 구현하는 크루스칼 알고리즘의 기반이 되는 유니온파인드 알고리즘을 사용하는 문제이다.

 

getParent함수는 재귀함수로, 해당 노드의 부모 노드를 찾는 노드이다.

unionParent함수는 간선에 해당하는 두 개의 노드를 이어서 작은 부모 노드의 값으로 초기화한다.

findParent함수는 노드 a와 노드 b가 이어져 있는지, 즉 a와 b의 부모 노드가 같은지 확인한다.

크루스칼 알고리즘 문제 :

https://ongveloper.tistory.com/95

백준 1197 최소 스패닝 트리 c++ (크루스칼)

https://ongveloper.tistory.com/93

프로그래머스 섬 연결하기 c++ (탐욕법,크루스칼)

코드

#include<iostream>
#include<vector>

using namespace std;
int n, m;
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 findParent(int a, int b) {
    a = getParent(a);
    b = getParent(b);
    if (a == b) cout << "YES\n";
    else cout << "NO\n";
}


int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.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연산
            unionParent(a, b);
        }
        else { //find연산
            findParent(a, b);
        }

    }

    return 0;
}