[BOJ]1865번: 웜홀

 

www.acmicpc.net/problem/1865

---

라이님 블로그(blog.naver.com/kks227/220796963742)의 풀이를 참고하여 해결했습니다.

 

임의의 정점에 대해 모두 벨만포드를 돌 수 없으므로 

그래프를 BFS 탐색을 통해 컴포넌트로 나눠주고, 각 각의 컴포넌트에 대해서만 한 번씩 벨만포드를 돌면 됩니다.

하나의 컴포넌트라도 컴포넌트내에 음의 싸이클이 있다면 YES, 아니면 NO를 출력하면 됩니다.

---

코드: github.com/cottory/algorithm/blob/master/BOJ/BOJ1865.cc