[Algorithm] 34강 : 서로소 집합을 활용한 사이클 판별

서로소 집합 사이클 판별 1.1 서로소 집합 사이클 판별이란? 서로소 집합은 무방향 그래프 내에서의 사이클을 판별할 때 사용할 수 있다. 참고로 방향 그래프에서 사이클 여부는 DFS를 이용하여 판별할 수 있다. 사이크 판별 알고리즘은 다음과 같다. 각 간선을 하나씩 확인하며 두 노드의 루트 노드를 확인한다 루트 노드가 서로 다르다면 두 노드에 대하여 합집합 연산을 수행한다 루트 노드가 서로 같다면 사이클이 발생한다 그래프에 포함되어 있는 모든 간선에 대하여 1번 과정을 반복 1.2 동작과정 선의 연결 여부를 확인한 후 연결된 상태면 부모 노드를 1로 연결한다. 이때 모든 루트 노드가 같으면 사이클이 발생했다고 한다. 1.3 구현 # 특정 원소가 속한 집합을 찾기 def find_parent(parent,..