outdegree가 0인 모든 SCC의 정점들을 출력하는 방법으로 ac를 받았습니다.


그런데 개인적으로 궁금한 것이, bottom(G)가 공집합이기 위해서는 모든 SCC의 outdegree가 1 이상이어야 하는데 이런 경우가 존재하나요?


모든 SCC의 outdegree가 1 이상인 경우가 존재한다고 가정하면, 항상 SCC 간의 사이클이 생기고, 따라서 SCC의 정의에 어긋나므로 모순이지 않나요? SCC 그래프는 DAG이고, 그래프가 DAG라면 언제나 outdegree가 0인 정점이 하나 이상 있지 않나요?

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