위상정렬 알고리즘 -큐를 이용 1. 진입차수가 0인 모든 노드를 큐에 넣는다. 2. 큐가 빌 때까지 다음의 과정을 반복한다. 1) 큐에서 원소를 꺼내 해당 노드에서 나가는 간선을 그래프에서 제거한다. 2) 새롭게 진입차수가 0이 된 노드를 큐에 넣는다. --> 결과적으로 각 노드가 큐에 들어온 순서가 위상 정렬을 수행한 결과와 같다. (특징) - 사이클이 없는 방향그래프(DAG)여야 한다. - 한 단계에서 큐에 새롭게 들어가는 원소가 2개 이상인 경우가 있다면 여러가지 답 존재. - 모든 원소를 방문하기 전에 큐가 빈다면 사이클이 존재한다고 판단할 수 있음 (시간복잡도) - 차례대로 모든 노드를 확인하며 각 노드에서 나가는 간선을 차례대로 제거하므로 시간복잡도는 O(V+E)이다. 위상정렬 코드 from ..