https://www.acmicpc.net/problem/14591
14591번: KUBC League (Large)
고려대학교 중앙 배드민턴 동아리 KUBC에서 정회원들을 대상으로 리그를 했다. 태양이를 포함해서 N명의 정회원들이 리그에 참여했고, 총 N(N-1)/2번의 경기를 진행하였다. 그 결과 모든 경기가 승
www.acmicpc.net
먼저 모든 정점에 대해 p가 q를 이기면 p -> q 간선을 만들어준다.
그 다음 dfs트리를 만들어 보자.
그러면 이런 모양이 나온다.(정점 번호는 방문 순서)
정답은 그냥 빨간색 edge를 따라가서 방문하는 모든 정점을 출력하면 된다.
왜냐하면 어떤 정점 p의 부모 노드가 아니면서 dfs트리 방문 순서가 p보다 먼저라면 p에서 그 정점으로 향하는 간선이 있기 때문이다.(p가 이긴다는 뜻)
그리고 이 빨간 edge들은 잘 보면 위상정렬을 dfs로 했을 때 나오는 결과와 같다.
반대로 바로 dfs 위상정렬을 떠올릴 수도 있다.
원래 사이클이 있는 그래프는 위상정렬이 불가능하지만 이 문제는 dfs 위상정렬을 했을 때 생기는 back edge들을 무시해도 되기 때문이다.