수학과의 좌충우돌 프로그래밍

유니온 파인드 알고리즘이란? 그래프 알고리즘의 일종으로서 상호 배타적 집합, Disjoint-set 이라고도 합니다. 여러 노드가 존재할 때 어떤 두 개의 노드를 같은 집합으로 묶어주고, 다시 어떤 두 노드가 같은 집합에 있는지 확인하는 알고리즘입니다. 그러기 위해 두 가지 연산이 존재합니다. Find 노드 x 가 어느 집합에 포함되어 있는지 찾는 연산 Union 노드 x가 포함된 집합과 노드 y가 포함된 집합을 합치는 연산 유니온 파인드 구현 구현은 간단한 트리를 통해서 이루어집니다. parent[i] 를 i 노드의 부모 노드 라고 정의하고 초기화 해줍니다. parent[i] = i 인 경우, 루트노드 임을 의미합니다. int parent[MAX_SIZE]; for (int i=0; i