BOJ 3665 최종 순위

https://www.acmicpc.net/problem/3665
시간 1초, 메모리 256MB

input :

• 테스트케이스의 수 T
• n (2 ≤ n ≤ 500)
• n개의 정수 ti를 포함하고 있는 한 줄. (1 ≤ ti ≤ n)
• m (0 ≤ m ≤ 25000)
• ai bi m줄. (1 ≤ ai < bi ≤ n)

output :

• n개의 정수를 한 줄에 출력 (1등팀부터 순서대로 출력)
• 확실한 순위를 찾을 수 없다면 "?"를 출력
• 데이터에 일관성이 없어서 순위를 정할 수 없는 경우에는 "IMPOSSIBLE"을 출력

조건 :

• 팀은 1번부터 n번까지 번호
• 작년에 비해서 상대적인 순위가 바뀐 팀의 목록만 발표
• 작년 순위와 상대적인 순위가 바뀐 모든 팀의 목록이 주어졌을 때, 올해 순위를 만드는 프로그램을 작성

---

idea

주의

해당 문제의 테케가 매우 빈약해서 "?"를 출력하는 경우 자체가 없다.
이거 넣으면 뱃지 받을 수 있을 거 같긴 한데 귀찮으니 넘기고.

꼴등이 진입차수 0을 할지, 1등이 진입차수 0을 할지를 정해야 한다.
1등이 진입 차수 0으로 했기 때문에 graph[높은 등수][낮은 등수]로 딕셔너리에 저장한다.

?, IMPOSSIBLE 조건
위의 링크에 따라서 조건을 만들었다.

import sys
from collections import deque

t = int(sys.stdin.readline())
for _ in range(t):
    n = int(sys.stdin.readline())
    prev = list(map(int, sys.stdin.readline().split()))
    m = int(sys.stdin.readline())
    degree = [0] * (n + 1)
    graph = [dict() for _ in range(n + 1)]

    for i in range(n - 1, 0, -1):
        node = prev[i]
        degree[node] = i

        for j in range(i - 1, -1, -1):
            next_node = prev[j]
            graph[next_node][node] = 1


    now_degree = [i for i in degree]
    for i in range(m):
        a, b = map(int, sys.stdin.readline().split())
        if degree[a] > degree[b]:
            del graph[b][a]
            graph[a][b] = 1
            now_degree[a] -= 1
            now_degree[b] += 1
        else:
            del graph[a][b]
            graph[b][a] = 1
            now_degree[b] -= 1
            now_degree[a] += 1

    q = deque([])
    for i in range(1, n + 1):
        if now_degree[i] == 0:
            q.append(i)

    ans = []
    while q and len(q) < 2:
        node = q.popleft()
        ans.append(node)

        for next_node in graph[node].keys():
            now_degree[next_node] -= 1
            if now_degree[next_node] == 0:
                q.append(next_node)

    if len(q) > 1:
        print("?")
    elif len(ans) != n:
        print("IMPOSSIBLE")
    else:
        print(*ans)