다양한 알고리즘 - 서로소 집합을 활용한 사이클 판별
안녕하세요. 서로소 집합은 다양한 알고리즘에 사용될 수 있습니다. 특히 서로소 집합은 무방향 그래프 내에서의 사이클을 판별할 때 사용할 수 있다는 특징이 있습니다. 앞서 union 연산은 그래프에서의 간선으로 표현될 수 있다고 했습니다. 따라서 간선을 하나씩 확인하면서 두 노드가 포함되어 있는 집합을 합치는 과정을 반복하는 것만으로도 사이클을 판별할 수 있습니다. 과정 1번) 각 간선을 확인하며 두 노드의 루트 노드를 확인합니다. 루트 노드가 서로 다르다면 두 노드에 대하여 union 연산을 수행합니다. 루트 노드가 서로 같다면 사이클(Cycle)이 발생한 것입니다. 2번) 그래프에 포함되어 있는 모든 간선에 대하여 1번 과정을 반복합니다. 예시 1 / \ 2---3 초기 상태에서는 모든 노드는 자기 자..
