qocn9029   3년 전

그래프 탐색중 사이클의 존재를 알아내려면 현재 방문하고 있는 노드에서 현재방문하고 있는 노드와 인접한 노드들중 이미 방문했던 노드가 발견될때

이를 사이클이 존재한다라고 확신 할수 있나요??

xkdlaldfjtnl   3년 전

넵 그렇죠 

그 사이클 유무를 확인하는 경우에 대한 알고리즘은 Union-find 알고리즘이 있고, 대표적으로

https://www.acmicpc.net/proble... 20040문제 보시면 될 것 같습니다.

보시면 될것같습니다.

댓글을 작성하려면 로그인해야 합니다.