합집합 연산

[c++] 백준 1717 풀이 (집합의 표현, 그래프, 서로소 집합, 유니온파인드)

서로서 집합은 상호 배타적 집합(Disjoint-set) 이라고 한다. 교집합이 공집합인 집합(서로소 집합) 들의 정보를 확인하고 조작할 수 있는 자료구조이다. - union : 두 노드를 한 그래프로 합친다. - find : 어떤 노드가 속한 집합을 반환 이 문제는 유니온 파인드를 이용하여 두 노드가 해당하는 집합을 합치거나 한 노드가 다른 노드의 집합에 속하는지 판별하는 문제이다. 따라서 union함수를 구현하고, find함수를 구현하여 풀이를 진행한다. 우선 find함수를 구현한다. find함수의 역할은 해당 노드의 부모로 탐색을 진행한다. 따라서 루트 노드를 만나는 경우 반환을 진행하며, 루트 노드가 아닌 경우에는 해당 노드의 부모에 루트 노드 값을 입력해준다. (즉 find과정을 통해 tree를..