Topological DP

indegree → queue → order → dp 순서로 한 방향 전개

DAG에서는 간선이 되돌아오지 않으므로 위상 정렬로 계산 순서를 먼저 만들고, 그 순서 위에서 DP 값을 전파합니다.

indegree 각 정점 앞의 선행 간선 수 [0,1,1,2]
queue indegree 0인 정점 [1]
order 선행 조건을 만족한 순서 1,2,3,4
위상 정렬 후 DP 값이 1에서 4까지 전파됨 1 2 3 4
Kahn

queue에서 indegree 0 정점을 반복해 꺼냅니다.

DFS 순서

완료 시간 역순을 쓰되 색 배열로 사이클을 봅니다.

DAG DP

위상 순서대로 처리해 이전 상태가 이미 확정됩니다.

Cycle

남은 indegree가 있으면 순서를 정할 수 없습니다.

초기 queue indegree가 0인 모든 정점을 넣었는가.
처리 수 위상 정렬 결과 길이가 정점 수와 같은가.
DP 방향 간선 방향과 점화식 전파 방향이 일치하는가.