최종 순위

• 쉽게 떠오르는 것은 위상 정렬 (Topological Sorting)이다. 순위가 높은 쪽에서 순위가 낮은 쪽으로 엣지를 만들고, 위상정렬을 돌려보다가 사이클이 존재한다면 “IMPOSSIBLE”을, 그렇지 않으면 위상정렬 결과를 출력하면 된다.
• 작년의 모든 순위 정보와, 올해에 순위가 바뀐 '모든' 팀 목록을 주기 때문에, 확실한 순위를 찾을수 없는 경우 (=가능한 순위가 여러개인 경우)는 존재하지 않는다. 그럴 경우에 '?'를 출력하라는 것은 그냥 함정이니 무시하면 된다.
• 다만 이렇게 한다면, 처음에 그래프를 만들때 (x, y)쌍에 대해서 n*(n-1)/2 개의 엣지를 만들어 줘야 한다. 그 뒤에 순위가 변경된 쌍들 (a_i,b_i)에 대해서 a_i ⇒ b_i 로의 엣지를 지우고 b_i ⇒ a_i로의 엣지를 추가해야 한다. (만약 처음 그래프에 b_i⇒a_i 엣지가 있었다면 그걸 지우고 a_i⇒b_i로의 엣지를 추가한다). 결국 총 엣지수는 변하지 않는다. 엣지의 갯수 |E|가 O(|V|^2)이므로 총 위상정렬의 총 시간 복잡도는 O(|V|+|E|) = O(|V|^2) = O(n^2) 가 걸린다.
• 그냥 순위가 바뀐 쌍에 대해서만 엣지를 추가해주고, 그리고는 그냥 위상정렬을 돌리면서, 다음 방문가능한 번호가 여러개일 때에는 '작년 순위'가 작은 번호를 먼저 꺼내는 식으로 처리를 해도 되기는 할것 같다. 그러면 엣지의 수는 m으로 줄고, 대신 위상정렬 안에서 우선순위큐를 써야 하니까 시간 복잡도가 O(nlogn + m)으로 해결될것 같다. 그러나 이 방법으로는 조건이 제대로 주어졌을때는 맞는 답을 찾지만, 'IMPOSSIBLE'인 경우를 제대로 디텍트하지 못한다. 이것만 빠르게 처리할수 있으면 가능할것 같은데 방법이 간단하게는 잘 안떠오른다.
• 그리고, 가장 간단한 방법은, 위상정렬 자체를 쓰지 않는 방법이다. 어떤 팀의 순위를 다르게 표현하면 '그 팀보다 순위가 높은 팀'의 갯수이다. 각 팀에 대해서 작년의 순위, 즉 작년에 '자신보다 순위가 높은 팀의 갯수'로 prev_rank[x]와 cur_rank[x]를 초기화해두고, 올해 순위가 변경된 쌍들 (a_i,b_i)에 대해서 작년에 b_i가 a_i보다 순위가 높았다면, cur_rank[b_i]를 1증가, cur_rank[a_i]를 1감소시키는 방식으로 올해 순위를 갱신하는 것이다. 모든 m에 대해서 처리한 뒤, cur_rank에 1~n까지가 다 들어있다면 정상적인 결과이니까 정렬해서 출력하면 되고, 그렇지 않으면 'IMPOSSIBLE'을 출력한다. 마지막에 출력하기 위해서 정렬하는 것을 제외하면 O(n+m)이고, 정렬하는데에 O(nlogn)을 합쳐서 O(nlogn+m)이다. 카운팅소트와 비슷한 방법으로 처리하면 O(n+m)에도 가능.
  • 실제 구현은 카운팅소트는 쓰지 않고 O(nlogn+m)에 풀었다. 위상정렬로 O(n^2)에 풀었을때에는 약 1200ms, 이 방식으로 풀었을때는 약 170ms가 걸렸다.

"""Solution code for "BOJ 3665. 최종 순위".

- Problem link: https://www.acmicpc.net/problem/3665
- Solution link: http://www.teferi.net/ps/problems/boj/3665

Tags: [TopologicalSort]
"""

import graphlib
import sys


def main():
    test_case_count = int(sys.stdin.readline())
    for _ in range(test_case_count):
        n = int(sys.stdin.readline())  # pylint: disable=unused-variable
        t = [int(x) for x in sys.stdin.readline().split()]
        pred_graph = {}
        preds = set()
        for t_i in t:
            pred_graph[t_i - 1] = preds
            preds = preds | {t_i - 1}
        m = int(sys.stdin.readline())
        for _ in range(m):
            a, b = [int(x) for x in sys.stdin.readline().split()]
            if b - 1 in pred_graph[a - 1]:
                pred_graph[a - 1].remove(b - 1)
                pred_graph[b - 1].add(a - 1)
            else:
                pred_graph[b - 1].remove(a - 1)
                pred_graph[a - 1].add(b - 1)

        try:
            order = graphlib.TopologicalSorter(pred_graph).static_order()
            print(*(u + 1 for u in order))
        except graphlib.CycleError:
            print('IMPOSSIBLE')


if __name__ == '__main__':
    main()

"""Solution code for "BOJ 3665. 최종 순위".

- Problem link: https://www.acmicpc.net/problem/3665
- Solution link: http://www.teferi.net/ps/problems/boj/3665

Tags: [Sort]
"""

import sys


def main():
    test_case_count = int(sys.stdin.readline())
    for _ in range(test_case_count):
        n = int(sys.stdin.readline())
        t = [int(x) for x in sys.stdin.readline().split()]
        orig_rank =[None] * (n + 1)
        for i, t_i in enumerate(t):
            orig_rank[t_i] = i
        m = int(sys.stdin.readline())
        new_rank = orig_rank[:]
        for _ in range(m):
            a, b = [int(x) for x in sys.stdin.readline().split()]
            if orig_rank[a] < orig_rank[b]:
                new_rank[a] += 1
                new_rank[b] -= 1
            else:
                new_rank[a] -= 1
                new_rank[b] += 1

        if len(set(new_rank)) != n + 1:
            print('IMPOSSIBLE')
        else:
            print(*sorted(range(1, n + 1), key=new_rank.__getitem__))


if __name__ == '__main__':
    main()