[PS] Union-Find(유니온-파인드)

<!-- 작성중인 게시글입니다. -->

#include <iostream>
#define MAX 10

int parent[MAX];

int GetParent(int x) {
	if (x == parent[x]) return x;
    return parent[x] = GetParent(parent[x]);
}

int UnionParent(int a, int b) {
    a = GetParent(a);
    b = GetParent(b);
    if (a < b) parent[b] = a; // 더 작은쪽으로 부모를 설정한다고 가정
    else parent[a] = b;
}

bool SameParent(int a, int b) {
    a = GetParent(a);
    b = GetParent(b);

    if (a == b) return 1;
    else return 0;
}

int main(void) {
    for (int i = 0; i < MAX; i++) parent[i] = i;
    UnionParent(1, 2);
    UnionParent(2, 3);
    UnionParent(3, 4);
    UnionParent(5, 6);
    UnionParent(6, 7);
    UnionParent(7, 8);
    for (int i = 0; i < MAX; i++) std::cout << parent[i] << ' ';
    std::cout << '\n';
    UnionParent(1, 5);
    for (int i = 0; i < MAX; i++) std::cout << parent[i] << ' ';
}

 

관련 문제

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