진입 차수 0 정점을 모두 제거할 수 있으면 DAG다
Kahn 알고리즘은 위상 순서를 만들면서 동시에 사이클 여부를 판정합니다.
제거 흐름
01indegree 0을 큐에 넣음
02꺼낸 정점을 처리
03나가는 간선의 indegree 감소
04seen == V인지 확인
핵심: 위상성 검사는 “정렬 결과”보다 “처리한 정점 수가 전체와 같은가”가 판정 기준입니다.
Kahn 알고리즘은 위상 순서를 만들면서 동시에 사이클 여부를 판정합니다.
핵심: 위상성 검사는 “정렬 결과”보다 “처리한 정점 수가 전체와 같은가”가 판정 기준입니다.