Logo
(追記) (追記ここまで)

bottom(G)가 공집합인 경우가 존재하나요?

6543번 - 그래프의 싱크

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


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


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

비록 4년 전 글이지만 다른 분들 보시라고 남겨둡니다.

bottom(G)가 공집합일 경우 while (1)로 시간 초과를 유도했으나 별 문제 없이 통과됩니다.

bottom(G)가 공집합인 테스트 케이스는 존재하지 않는 듯 합니다. 이 점은 신경 쓰지 않으셔도 될 것 같습니다.

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

(追記) (追記ここまで)

출처

대학교 대회

  • 사업자 등록 번호: 541-88-00682
  • 대표자명: 최백준
  • 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
  • 전화번호: 02-521-0487 (이메일로 연락 주세요)
  • 이메일: contacts@startlink.io
  • 통신판매신고번호: 제 2017-서울서초-2193 호

AltStyle によって変換されたページ (->オリジナル) /