위상 정렬과 DAG DP

진입 차수 계산

각 정점 앞에 남아 있는 선행 조건 수를 indegree 배열에 저장한다.

0인 정점부터 처리한다

queue에서 꺼낸 정점은 더 이상 기다릴 선행 작업이 없으므로 전이를 실행할 수 있다.

사이클을 검출한다

처리한 정점 수가 n보다 작으면 indegree가 0이 되지 못한 사이클이 남은 것이다.

Kahn

queue 기반 위상 정렬 indegree가 0인 정점을 반복해서 꺼낸다.

여러 정답 순서가 가능하다.

DFS 순서

완료 시간 역순 DFS가 끝난 순서를 뒤집어 위상 순서를 얻는다.

사이클 검사는 색 배열이 필요하다.

DAG DP

순서 보장 전이 위상 순서대로 처리하면 이전 상태가 이미 확정되어 있다.

초기값이 매우 중요하다.

Cycle

위상 순서 불가 남은 indegree가 있는 정점은 순서를 정할 수 없다.

문제에서 DAG 보장을 확인한다.

초기 queue · 처리 수 · DP 방향 점검

초기 queue indegree가 0인 모든 정점을 처음에 넣었는가.

처리 수 위상 정렬 결과 길이가 정점 수와 같은가.

DP 방향 간선 방향과 점화식 전파 방향이 일치하는가.

진입 차수 흐름

for (int v : zero) q.push(v);
while (!q.empty()) {
    int v = q.front(); q.pop(); order.push_back(v);
    for (int to : g[v]) if (--indeg[to] == 0) q.push(to);
}