[일반] Directed graph에서 네거티브 사이클 찾는거

[익명(172.226)]

꼭 벨만포드 돌려야함?
다른 방법은 없냐

[익명(apg2fwpfgsz5)]

그래프의 모든 간선 순회하는건 해야할껄. 굳이 벨만포드가 아니여도 되긴함

[익명(119.206)]

음수 사이클 검출 문제 보면 벨만포드보다 더 빠른 방법으로 푼사람들이 많이 있긴한데, 걍 벨만포드 딸깍 캐뤼가 편하긴 한거같음

[익명(178.88)]

O(E)

[익명(223.62)]

잠깐 생각해봤는데 SCC 구한 다음 음의 간선 중에 같은 SCC 안의 정점을 잇는 게 있으면 거기에 음의 사이클이 있을 가능성이 있지 않을까? 그게 있다고 무조건 음의 사이클인 건 아니긴 한데 여기서부터 시작하면 뭔가 나오지 않을까 싶음