DAG DP gate

사이클, 초기값, 전이 방향을 통과한 뒤 DP를 시작한다

DAG DP는 점화식보다 먼저 “위상 순서로 한 번만 흘러도 되는가”를 검증해야 한다.

1. cycle위상 정렬 결과가 V개인가?

2. base시작 정점의 dp가 먼저 채워졌는가?

3. direction간선 방향으로만 값이 흐르는가?

검증 지점	통과 기준	실패 신호	고정 방법
위상 순서	`order.length === V`	일부 정점이 order에 없음	cycle 또는 indegree 계산을 먼저 수정
초기값	source/base만 0 또는 1	INF/0이 모든 정점에 깔림	문제 의미에 맞는 base를 한 곳에 고정
전이 방향	`for (u of order) for (v of adj[u])`	역방향 간선으로 값 전파	간선 의미와 점화식 방향을 맞춤
갱신 연산	max/min/count 중 하나	비교식과 초기값 불일치	목표 함수에 따라 연산을 표로 고정

핵심: DAG DP는 “사이클 없음 → base 고정 → 위상 순서 전파” 순서가 깨지면 바로 오답이다.