서로소 집합 알고리즘(3)/ 사이클 판별

나동빈님의 '이것이 코딩테스트다 with 파이썬'저서와 유튜브 강의를 참고하며 작성하였습니다. 

코드 출처: https://github.com/ndb796/python-for-coding-test

---

▶ 사이클 판별

서로소 집합 알고리즘을 무방향 그래프 내에서 사이클이 발생하는지(서로 연결되어 순환할 수 있는 구조인지) 판별하는데 사용할 수 있다.

 

 

 

▶ 작동 과정

step 1. 각 간선을 확인하며 루트노드를 보았을 때 루트 노드가 같다면 사이클이 발생한 것이고, 같지 않으면 두 노드에 대한 union연산을 수행한다. 

step 2. 모든 간선에 대해 step1을 반복한다.

 

 

▷ 예시

아래와 같은 그래프가 있다고 해보자. 1,2,3 노드에서 사이클이 발생하고 있으므로 사이클이 존재하는 그래프이다.

작동 과정을 경로 압축기법을 사용하여 기술해보았다.

 

step 1. 1과 2 노드를 보자. 노드 1의 루트노드 1과 노드 2의 루트노드 2가 다르므로 union연산을 수행한다. 노드 2의 부모노드가 1로 갱신된다. 

 

step1. 1과 3노드를 보자. 노드 1의 루트노드는1, 노드3의 루트노드는 3이므로 노드3의 부모노드를 1로 바꿔준다. 

 

 

step1. 2와 3을 보자. 노드 2의 루트노드는 1, 노드 3의 루트노드는 1이다. 두 노드의 루트노드가 같으므로 1,2,3 노드까지는 사이클이 발생한 것이다. 

 

step1. 마지막으로 1과 4를 보자. 노드 1의 루트노드는 1, 노드 4의 루트노드는 4이므로 노드 4의 부모노드를 1로 바꿔준다. 

step 2. 모든 간선에 대해 연산을 수행했으므로 종료된다. 

 

 

▷ 구현 

 

특정원소가 속한 루트노드와 union연산 함수는 이전과 동일하다. 

 

 사이클이 발생하는 순간(두 노드의 루트노드가 동일한 경우) 함수가 종료되도록 하였다.