서로소 집합 연산을 통해 Cycle을 확인하는 방법의 궁금증의 답

( 궁금했던 내용을 확인해보려면 : https://the-bingle.tistory.com/85 )

 

 나온 자료들에대해 내가 잘 못 알고 있었다.

 

 union은 둘의 root를 연결하는 연산

 find는 root노드를 찾는 것.

 이렇게 분리하고 인식해야 했다.

 

 간선에대해서

 양 노드의 루트 노드를 find를 이용해 찾고, 이 두개의 루트 노드가 동일하다면 cycle

 동일하지 않다면, union을 통해 둘의 루트 노드를 연결하는 것이다.

 

 이 과정을 반복하면 되는데,

 

 union을 통해, 두 노드의 루트노드가 같아지는건 연결되어있음을 의미하고, 당연한 결과이다.

 간선에대해서 라는 부분이 확인하는 지점임을 생각하자.