반응형 disjoint set1 [C++] Union-Find 알고리즘 Union-Find 알고리즘은 중복되지 않은 원소들로 이루어진 집합들을 표현할 때 사용하는 알고리즘이다.아래와 같이 간단하게 구현할 수 있는 자료구조로, 코딩테스트에서는 중복되지 않는 id를 가지는 집들이 있을 때, 거리별로 마을이 만들어진다던가 하는 문제에서 활용하기 좋다.#include using namespace std;int parents[11];void init() { for (int i = 1; i 출력값은 1 2 3 4 5 6 7 8 9 10 1 2 3 4 5 6 7 1 2 1 1 1 3 4 5 6 7 1 2 1으로, 1번 노드와 10번 노드, 10번 노드와 8번 노드, 2번 노드와 9번 노드가 합쳐졌을 때 각각 부모노드는 1번, 2번으로 잘 합쳐진 것을 확인할 수 있다.최종적으로.. 2024. 6. 24. 이전 1 다음 반응형
