topological cover
위상 순서는 모든 정점을 덮어야 DP 값이 의미 있다
위상 정렬 결과가 짧으면 일부 정점의 선행 조건이 끝나지 않았다는 뜻이다.
정상: N개 모두 포함
1
2
3
4
실패: 일부 정점 누락
1
2
?
?
상태
의미
판정
queue empty
더 이상 indegree 0 정점이 없음
order가 짧으면 cycle 의심
remaining indegree
선행 간선이 지워지지 않은 정점
DP 전제 실패
full order
모든 정점이 한 번씩 확정됨
이때만 DP 전파 시작
핵심: order가 N보다 작으면 값을 채우는 문제가 아니라 그래프가 DAG인지부터 다시 확인해야 한다.