[백준]3665 최종순위(Python)

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

3665번: 최종 순위

 

문제 접근 

 

5번과 3번의 상대적인 순위 관계가 바뀐다면,

5번그래프에 3번을 빼주어야 하고

3번 그래프에 5를 넣어주어야 한다.

=> 3번으로 들어오는 간선이 하나 줄어들고, 5번으로 들어오는 간선이 하나 늘어났으므로

차수(indegree)도 변경

 

데이터에 일관성이 없어서 순위를 정할 수 없는 경우에는 "IMPOSSIBLE"을 출력

한 번에 2개 이상의 원소가 들어간다는 것은 진입차수가 0인 원소가 두개 이상

=> 사이클 발생 

 

코드

from collections import deque
import sys

input = sys.stdin.readline

t = int(input())

for i in range(t):
    n = int(input())

    graph = [[] for _ in range(n + 1)]
    inDegree = [0 for _ in range(n + 1)]
    queue = deque()
    answer = []
    flag = 0

    team = list(map(int, input().split()))

    for j in range(n - 1):
        for k in range(j + 1, n):
            graph[team[j]].append(team[k])
            inDegree[team[k]] += 1

    m = int(sys.stdin.readline())
    for j in range(m):
        first, second = map(int, input().split())
        flag = True

        for k in graph[first]:
            if k == second:
                graph[first].remove(second)
                inDegree[second] -= 1
                graph[second].append(first)
                inDegree[first] += 1
                flag = False

        if flag:
            graph[second].remove(first)
            inDegree[first] -= 1
            graph[first].append(second)
            inDegree[second] += 1

    for j in range(1, n + 1):
        if inDegree[j] == 0:
            queue.append(j)

    if not queue:
        print("IMPOSSIBLE")
        continue

    result = True
    while queue:
        if len(queue) > 1:
            result = False
            break

        tmp = queue.popleft()
        answer.append(tmp)
        for j in graph[tmp]:
            inDegree[j] -= 1
            if inDegree[j] == 0:
                queue.append(j)
            elif inDegree[j] < 0:
                result = False
                break

    if not result or len(answer) < n:
        print("IMPOSSIBLE")
    else:
        print(*answer)