Union Find5 [Union find] c++ 구현 및 설명 목차 Union find (분리 집합) 정의 서로소 집합이라고 불리며 공통 원소를 가지지 않는 집합을 말한다. 예를 들면 1그룹과 2그룹이 있을 때 관계의 확인을 위해 일일히 bfs, dfs를 돌리는 것은 비효율적이므로 자기 그룹의 꼭대기에 있는 사람만 비교하는 것이다. 2와 8은 다른 그룹인 것을 알 수 있다. 트리에 값 추가하는 방법 parent[2] = 3; parent[7] = 3; parent[5] = 3; parent[8] = 4; 두 수가 같은 집합인지 알기 위해 필요한 함수 int find_root(int node) { if (parent[node].first == node) return node; //노드의 최적화: 항상 부모를 루트노드로 만듬 return parent[node] = fi.. 2024. 2. 22. 이전 1 2 다음 728x90
