3개의 댓글이 있습니다.
-
-
JongMan -
안녕하세요? 결론부터 말씀드리자면 지적하신 내용이 맞습니다. ㅠ.ㅠ 왜 이런 오류를 냈는지 모르겠네요 이런 심각한 오류라니...
문제는 dfs 도중 검사하는 간선이 트리 간선이 아닐 때 있습니다. 해당 간선이 교차 간선인지, 순방향/역방향 간선인지를 보는 대신, 간선의 반대쪽 끝 정점이 스택에 들어 있는지를 살펴야 합니다.
따라서
else if(discovered[there] < ...)이 조건문을else if(sccId[there] == -1)로 바꿀 경우 정상적으로 동작할 것으로 여겨집니다.혼란을 드려 죄송합니다. 곧 홈페이지에 정오표를 업로드하고 다음 쇄에서 반드시 수정하도록 하겠습니다.
10년 전 link
-
-
정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.
Signin
JMBook 2권 28단원에,
tarjan의 SCC 분리 알고리즘이 있습니다.
그런데 특정 그래프에 대해서는
분리되지 않아야 하는 SCC가 분리되게 됩니다.
여기에 그림을 올리지 못해서 다른 곳에 글을 썼습니다.
이 내용이 맞는지 한 번 살펴봐주시면 감사하겠습니다.
링크
10년 전