edwardblue   4년 전

타잔 알고리즘을 이용해서 SCC를 구했는데 계속 틀렸다고 나옵니다.

어느 부분에서 오류가 있는지 알려주시면 감사하겠습니다.

pichulia   4년 전

scnt, vcnt가 0으로 초기화되있고

"방문하지 않은 정점"을 나태내는 값 d[i]도 0이고

"scc가 결정되지 않은 정점"을 나타내는 값 sccid[i]도 0입니다.

이렇게 되면 '첫 scc'는 sccid[i]가 0이 들어가게 되고

이 경우 scc가 결정되지 않았다고 오판을 하게 됩니다;;

아얘 -1로 초기화를 하거나 scnt, vcnt를 1로 초기화한 다음에 이후 코드를 갈아엎는게 나을듯 합니다.

이 문제랑은 관련없지만 getDAG() 함수 내부에서  48번째 줄의 for문은 m까지가 아니라 scnt까지 돌아야하지 않나 싶습니다.

edwardblue   4년 전

감사합니당 ><

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