DAG DP 핵심
점화식보다 먼저 위상 순서를 고정한다
모든 간선
u->v
에서 u가 v보다 먼저 처리될 때만
dp[v]
를 이미 확정된 값으로 갱신할 수 있습니다.
1에서 2와 3으로, 다시 4로 이어지는 DAG
1
indeg 0
2
after 1
3
after 1
4
after 2,3
01
진입차수 계산
남은 선행 간선 수를 센다.
02
0인 정점 큐
기다릴 조건이 없는 정점부터 꺼낸다.
03
order 생성
모든 u가 v보다 앞서는지 확인한다.
04
dp 전파
위상 순서대로 값만 앞으로 민다.
성공: order = [1, 2, 3, 4]
처리 정점 수가 전체와 같으므로 전이식이 안전합니다.
실패: order 길이 < V
사이클이 남아 아직 확정되지 않은 값을 다시 참조합니다.
초기값은 문제마다 다르다
최장 경로는
NEG_INF
, 경로 수는 0에서 시작합니다.