상호 배타적 집합(disjoint set) = Union-Find

http://mygumi.tistory.com/246

디스조인트 셋

유니온 파인드

#include <bits/stdc++.h>
 
using namespace std;
 
#define Max 10001
 
int parent[Max];
// parent[x] : x라는 노드가 가지고 있는 부모 노드의 번호는 parent[x]
 
// 부모 노드를 찾는 함수
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[b] = a; // b의 부모는 a
    else parent[a] = b;
}
 
// 같은 부모를 가지는 확인(현재 2개의 노드가 같은 그래프에 속하는지 확인)
int findParent(int a, int b)
{
    a = getParent(a);
    b = getParent(b);
 
    if (a == b) return 1;
    return 0;
}
 
int solution(int n, vector<vector<int>> edges) 
{
    int answer = 0;
    
    for (int i = 1; i <= n; i++)
        parent[i] = i;
 
    for (auto i : edges)
        unionParent(i.at(0), i.at(1));
    
    for (int i = 1; i <= n; i++)
        printf("%d의 부모는 %d입니다.\n", i, parent[i]);
 
    return answer;
}
 
int main(void)
{
    vector<vector<int> > vc = {
        {1, 2},
        {1, 3},
        {2, 3},
        {2, 4},
        {3, 4}
    };
 
    cout << solution(4, vc) << '\n';
 
    return 0;
}