백준 #3665 #Python

https://www.acmicpc.net/problem/3665

순서를 구하는 문제가 나오면 위상정렬로 풀 수 있는지 먼저 고려해봅시다.

1. 이 문제를 풀기 위해선 작년 순위를 기준으로 모든 간선들을 만들어 줘야 합니다.
   만약 1 3 2 라고 한다면
   1-3, 1-2, 3-2 간선을 모두 만들어야 합니다.
   (2번이 수행돼야 3번을 수행할 수 있고, 2, 3번이 수행돼야 1번이 수행될 수 있다고 생각하면 편함)

2. 순위가 바뀐 a, b는 서로의 부모 자식간의 관계가 뒤바꼈다고 볼 수 있습니다.

3. 이 문제는 작년의 순위가 주어지고 바뀐 모든 노드를 제시하기 때문에 "?"가 답이 되는 경우는 없습니다.
   따라서, 현재 수위를 나열했을 때 길이가 n이 아닌경우만 체크해주면 답이 나옵니다.

import sys
from collections import deque

input = sys.stdin.readline

tc = int(input())
ans = []

for _ in range(tc):
    n = int(input())
    rank = [0] + list(map(int, input().split()))

    nextOf = [set() for _ in range(n+1)]
    childCnt = [0]*(n+1)

    for i in range(1, n):
        childCnt[rank[i+1]] = i
        for j in range(i+1, n+1):
            nextOf[rank[i]].add(rank[j])

    m = int(input())

    for _ in range(m):
        a, b = map(int, input().split())
        if a in nextOf[b]: a, b = b, a
    
        nextOf[a].remove(b)
        nextOf[b].add(a)
        childCnt[b] -= 1
        childCnt[a] += 1
    
    que = deque()
    order = []

    for i in range(1, n+1):
        if childCnt[i] == 0:
            que.append(i)
            order.append(i)

    while que:
        now = que.popleft()
        for i in nextOf[now]:
            childCnt[i] -= 1
            if childCnt[i] == 0:
                que.append(i)
                order.append(i)

    if len(order) != n: ans.append("IMPOSSIBLE")
    else: ans.append(" ".join(map(str, order)))

print("\n".join(ans))