서로소 집합(Disjoint Set, Union-Find)

1717 집합의 표현 : https://www.acmicpc.net/problem/1717

0. 서로소 집합 => 트리로 표현!

- 교집합이 공징합인 집합들의 정보를 확인(Find)하고 조작(Union)할 수 있는 자료구조

- Union 연산

 : 어떤 두 원소에 대해 각 원소가 속한 집합을 하나로 합침

- Find 연산

 : 어떤 원소에 대해 해당 원소가 속한 집합을 반환

1. Find : 원소가 속한 집합의 대표번호 반환 = O(1)

int find(int a) { // root 노드 찾기

    if (a == node[a]) { return a; }

    else {

        return node[a] = find(node[a]);

    }

}

2. Union : 모든 원소를 순회하면서 하나의 집합 대표 번호를 다른 하나의 집합 대표 번호로 갱신한다 = O(N)

//***** b를 포함하는 집합의 root를 a를 포함하는 집합의 child로 둔다. *****

void union(int a, int b) {

    a = find(a);

    b = find(b);

    node[b] = a;

}