진입 차수 큐 처리
꺼낸 간선의 도착 정점 indegree를 줄이며 다음 후보를 찾습니다.
DAG 동적 계획법은 위상 순서 위에서만 앞으로 흐른다
Kahn 위상 정렬, indegree, dp[next], 경로 수 세기는 사이클 없는 방향 그래프라는 전제가 필요합니다.
위상 순서 DP 갱신
위상 순서가 없는 그래프에서는 값이 계속 커질 수 있으므로 DAG 확인을 선행 조건으로 둡니다.
현재 정점까지의 경우의 수를 다음 정점에 더해 갑니다
여러 부모에서 오는 누적을 놓치지 않아야 합니다.
위상 정렬 결과 검증
그 경우 DAG DP를 진행하면 안 됩니다.
방향성
u->v 간선은 dp가 이동할 수 있는 방향을 고정합니다.
초기값
시작 정점의 dp와 나머지 정점 값을 문제 의미에 맞게 둡니다.
복잡도
정점과 간선을 한 번씩 처리하므로 O(V+E)가 기본입니다.