sotter1020   5년 전

위상정렬에서 dfs가 종료되는 순서대로 찍고,

reverse를 하나요?

들어갈때 찍는거랑 순서가 다르지만,

선행노드는 잘나타내니까 상관없는거 아닌가요?

djm03178   5년 전

a -> c와 b -> c라는 간선이 있다고 합시다.

들어갈 때 출력을 하면 a c b 또는 b c a 둘 중 하나가 됩니다. 둘 중 어느 하나도 위상 정렬된 상태가 아니죠.

반면에 끝날 때 출력을 하면 c a b 또는 c b a 중 하나이고, 뒤집으면 b a c 또는 a b c로 위상 정렬이 잘 된 결과가 나옵니다.

sotter1020   5년 전

감사합니다!!

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