문제

#3665 최종순위

풀이

처음 보고 든 생각

어 이거 모든 노드가 연결되어있으면, 정확한 등수를알 수 있었던 정확한 순위 문제 생각이 나는디...

• 어떤 점이 다르지
  • 그냥 쌍만 주는게 아니라 작년의 순위 결과를 알려주고, 거기에서 순위가 뒤바뀐 쌍을 준다.
  • '일관성이 없는 잘못된 정보'를 "IMPOSSIBLE"로 출력해야
• 어떻게 하지
  • 작년 순위 결과를 바탕으로 그래프를 만들고, 거기에서 순위가 뒤바뀐 쌍을 적용하여 그래프를 보정한다.
  • 거기서 모든 노드와 연결되어 정확한 순위를 알 수 있는 노드의 순위를 출력하면 안될까요

풀이아이디어

위의 [처음보고 든 생각] 과 가깝다.
여기에서, '모든 노드와 연결되어 정확한 순위를 알기' 에 위상정렬 그래프 알고리즘이 들어간다.

위상정렬 그래프

• 목적 : 순서가 정해져 있는 작업을 차례로 수행해야할 때 그 순서를 결정하기 위해 이용
• 이 문제에서의 적용 : 순서 = 등수 정하기
• 시간복잡도 : O(V+E)

이 문제의 특이점

1. 사이클이 발생하는 경우
2. 위상 정렬의 결과가 1개가 아니라 여러 가지 인 경우
   에 해당하면 d