2252번: 줄 세우기 www.acmicpc.net 이 문제는 키를 비교한 두 학생의 번호 쌍들이 주어졌을 때 학생들을 키 순서대로 세우는 문제이다. 구체젹인 예로 1 3이라는 번호 쌍이 주어진 경우 학생 1이 학생 3보다 앞에 서야 한다. 즉, 학생 1과 학생 3 사이에는 어떤 학생이 와도 상관이 없으나 학생 1이 학생 3보다는 반드시 앞에 있어야 한다는 의미이다. 이러한 문제를 해결하기 위해서는 위상 정렬을 알아야 한다. 위상 정렬이란 directed acyclic 그래프(각 간선의 방향이 존재하고 사이클이 없는 그래프)에서 임의의 정점을 방문하기 위해 그 정점으로의 간선을 모두 방문해야 한다는 조건이 붙은 경우의 그래프 탐색 방법을 말한다. 위 문제의 경우를 예로 들어보자. 만약 어떤 학생 1이 학..
