문제

• 
• 시간 제한: 2초
• 메모리 제한: 128MB

Problem Analysis

A가 나온 이후에 B가 다음으로 나와야 한다. 이는 node A에서 node B로 가는 edge로 볼 수 있다. 또한, a->b->c->a 형태는 나올 수 없기 때문에, Cycle이 존재하지 않는다. 따라서, 일종의 Directed Acyclic Graph(DAG)로 볼 수 있고, 이를 순서를 거스르지 않도록 정렬해 주기만 하면 된다.

Algorithm

DFS를 통해 다음과 같이 Topological Sorting을 한다.
1. 현재 node의 인접 nodes로 recursive call을 한다.
2. call이 끝나고 난 이후에, 현재 node를 stack에 추가한다.
3. 모든 node를 방문할 때까지 1-2를 반복한다.
4. 하나씩 Stack에서 꺼내 출력한다.

Data Structure

• Stack[]: topological order를 저장

결과

Other

시간 복잡도는 DFS에 O(V+E)이므로, O(N+M)이다.