문제

[백준] 최종 순위 (Gold 1)

요약

  • 올해에는 작년과 비교해서 올해 상대적인 순위가 바뀐 두 팀만 발표한다. (작년에 더 낮았던/높았던 팀이 더 높아진/낮아진 경우만)
  • 작년의 순위가 주어진다.
  • 올해 최종 순위를 출력한다.
  • 만약 확실한 순위를 찾을 수 없다면 “?”를, 데이터에 일관성이 없다면 “IMPOSSIBLE”을 출력한다.

분류

  • 위상 정렬

풀이

1. 내 풀이 (위상 정렬)

  • 전형적인 위상정렬 문제이다.
  • 사이클이 생겼을 때, IMPOSSIBLE을 출력한다.
  • 상대적인 순위가 바뀌는 모든 경우를 말해주고, 전년도 순위 또한 확실하기 때문에 “?”는 고려하지 않아도 통과한다. (증명은…흠…몰라유)


import sys
from collections import deque
input = sys.stdin.readline

t = int(input())
for _ in range(t):
    n = int(input())
    graph = [set() for _ in range(n)]
    cnts = [0] * n
    last_year = list(map(int, input().split()))

    for i in range(n - 1):
        for j in range(i + 1, n):
            graph[last_year[i] - 1].add(last_year[j] - 1)
            cnts[last_year[j] - 1] += 1

    m = int(input())
    flag = False

    for _ in range(m):
        a, b = map(int, input().split())
        if b - 1 in graph[a - 1]:
            graph[a - 1].remove(b - 1)
            cnts[b - 1] -= 1
            graph[b - 1].add(a - 1)
            cnts[a - 1] += 1
        else:
            graph[b - 1].remove(a - 1)
            cnts[a - 1] -= 1
            graph[a - 1].add(b - 1)
            cnts[b - 1] += 1

    queue = deque([i for i in range(n) if cnts[i] == 0])
    ans = []
    while queue:
        cur = queue.popleft()
        ans.append(cur + 1)
        for i in graph[cur]:
            cnts[i] -= 1
            if cnts[i] == 0:
                queue.append(i)
    if sum(cnts) == 0:
        print(*ans)
    else:
        print("IMPOSSIBLE")