[알고리즘] 사이클 여부 판별하기

사이클 판별을 union find랑 dfs 두 방법으로 풀 수 있다.

이때 방향 그래프 여부에 따라 푸는 방법이 달라질 수 있다.

 

방향 그래프일 경우에는 연결되어있다고 사이클이 만들어지는 것이 아니기 때문이다!

 

사이클에 대한 최단경로를 플로이드워셜로도 구할 수 있다.

dp[A][B] + dp[B][A] 경로를 더하면 노드 A가 포함된 사이클의 최단경로가 되기 때문이다!

---

사이클 판별 문제들 모음

https://www.acmicpc.net/problem/20040

 

https://www.acmicpc.net/problem/10451

 

https://www.acmicpc.net/problem/5107

 

플로이드워셜로도 사이클을 구할 수 있다.

https://www.acmicpc.net/problem/1956