[Python/파이썬] - 백준(BOJ) 3665번 : 최종 순위

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

3665번: 최종 순위

 

태그는 위상 정렬으로 되어있지만 위상정렬을 사용할 필요 없는 문제.

 

처음에 등수 받을때 자신 밑에 몇명이 있는지 deg 배열에 저장한 후

상대적 순위가 바뀌었을 때 등수가 높은 사람은 deg 감소, 낮은 사람은 deg 증가시켜

deg 배열에 중복되는 숫자가 있는 경우 IMPOSSIBLE 출력.

 

변동된 상대적인 순위를 모두 입력받으므로 순위를 알수 없는 경우는 신경쓰지 않아도 된다.

 

import sys
input = sys.stdin.readline

for _ in range(int(input())):
    n = int(input())
    arr = list(map(int,input().split()))
    deg = [0] * n
    after = [0] * n
    for i in range(n):
        deg[arr[i]-1] = n-i-1
    m = int(input())
    for _ in range(m):
        a, b = map(int,input().split())
        a -= 1
        b -= 1
        if deg[a] > deg[b]:
            after[a] -= 1
            after[b] += 1
        else:
            after[a] += 1
            after[b] -= 1
    for i in range(n):
        deg[i] += after[i]
    answer = []
    b = 0
    for i in range(1, n+1):
        temp = []
        for j in range(n):
            if deg[j] == n-i:
                if temp:
                    b = 1
                    break
                temp.append(j+1)
                deg[j] = -1
        if b:
            break
        if not temp:
            b = 1
            break
        answer.append(temp[0])
    if b:
        print("IMPOSSIBLE")
    else:
        print(*answer,sep=' ')