https://www.acmicpc.net/problem/1613 1613번: 역사 첫째 줄에 첫 줄에 사건의 개수 n(400 이하의 자연수)과 알고 있는 사건의 전후 관계의 개수 k(50,000 이하의 자연수)가 주어진다. 다음 k줄에는 전후 관계를 알고 있는 두 사건의 번호가 주어진다. www.acmicpc.net 딱 보면 위상정렬로 착각하기 쉬운 문제입니다. 위상정렬보다는 훨씬 쉬운 방법으로 풀립니다. 위상정렬을 하듯이 생각해보면, 어떠한 사건 $a$가 사건 $b$보다 먼저 일어났다는 것은, $a$에서 $b$로 가는 단방향 간선이 존재한다고도 생각할 수 있습니다. 모순되는 사건이 존재하지 않는다고 했으므로, 그렇게 구성된 그래프는 항상 DAG의 형태를 띄게 됩니다. 그래프를 구성한 후 해당 그래프에..