Son's Warehouse

문제 출처 : https://algospot.com/judge/problem/read/DICTIONARY 이 문제에서 얻어 갈 수 포인트는 위상정렬을 한 후 유효성을 검증하는 것이다. 위상정렬은 DAG에서만 그 유효성을 입증 받을 수 있는데, 이 문제의 경우 주어진 그래프가 DAG가 아닐 수도 있다. 처음에 인접행렬방식으로 그래프를 만든다면, 위상정렬을 모두 마친 후 아래와 같은 방법으로 싸이클의 여부를 알아 낼 수 있다. 위상정렬한 결과 i번 노드와 j번 노드가 순서대로 있다면( i -> j ) j번째 노드에서 i번째로 가는 간선이 있다면 DAG가 아닌것이 되는 것이다. 그것을 인접행렬에서 모두 확인해 주면 된다.(인접 리스트라면 간선의 여부를 찾는데 시간이 더 소요될 것이다) 코드는 아래와 같다. 1..