작년에 팀13이 팀6보다 순위가 높았는데, 올해 팀6이 팀13보다 순위가 높다면, (6, 13)을 발표한다.
2 <= N <= 500
작년 순위와 상대적 순위가 바뀐 M개 팀의 목록이 주어졌을 때, 올해 순위를 만들어라.
0 <= M <= 25000
만약 확실한 순위를 찾을 수 없다면 ? 를 출력하고,
데이터 일관성이 없어 순위를 정할 수 없는 경우에는 "IMPOSSIBLE" 을 출력한다.
풀이
'순서' 라서 위상정렬을 떠올렸지만 어떻게 정렬할지 감을 못잡았다.
자신보다 순위가 낮은 팀을 가리키도록 방향 그래프를 만든 후 위상정렬을 수행해 순위를 매길 수 있다.
여기서, 사이클이 발생하면 IMPOSSIBLE 한 경우가 되고,
일반적인 위상정렬의 경우 N개의 노드를 큐에서 출력하지만 N번이 나오기 전에 큐가 비면 사이클이 발생한 것으로 볼 수 있다.
위상 정렬 결과가 1개가 아니라 여러 가지가 나오는 경우는 ? 을 출력해야할 경우가 된다.
큐에서 노드 뽑은 후 큐의 원소가 1개가 아니면 위상 정렬의 결과가 여러 개라고 볼 수 있다.
=> 위상 정렬 수행 과정에서 큐에서 노드를 뽑을 때 큐의 원소가 항상 1개로 유지되는 경우에만 고유 순위가 존재한다고 볼 수 있다.
from collections import deque
for _ inrange(int(input())): # 테스트 케이스 반복
N = int(input()) # 팀의 수
indegree = [0] * (N+1) # 진입 차수
graph = [[False]*(N+1) for _ inrange(N+1)] # 방향 그래프# 작년 순위 입력받기
data = list(map(int, input().split()))
for i inrange(N):
for j inrange(i+1, N):
graph[data[i]][data[j]] = True# i -> j 낮은 팀 가리키기
indegree[data[j]] += 1# 낮은 팀 진입차수 +1
M = int(input()) # 바뀐 순위 정보 개수for _ inrange(M):
a, b = map(int, input().split()) # a가 b보다 낮았는데 높아졌다# 간선 방향 뒤집기# 현재 a가 b보다 높은 경우if graph[a][b] :
graph[a][b] = False
graph[b][a] = True
indegree[a] += 1
indegree[b] -= 1# 현재 a가 b보다 낮은 경우else:
graph[a][b] = True
graph[b][a] = False
indegree[a] -= 1
indegree[b] += 1# 위상 정렬
result = [] # 순위 리스트
q = deque()
# 진입 차수 0인 노드 큐에 삽입for i inrange(1, N+1):
if indegree[i] == 0:
q.append(i)
only_one = True# 경우의 수가 하나인 경우
cycle = False# 사이클이 존재하는 경우for i inrange(N):
iflen(q) == 0 : # N번 반복 전에 큐가 비었다!
cycle = True# 사이클이 존재한다.breakiflen(q) >= 2: # 큐에 2개 이상의 노드가 있다!
only_one = False# 여러 개 경우의 수가 존재한다.break# 현재 노드와 연결된 노드들 진입차수 -1
now = q.popleft()
result.append(now)
for j inrange(1, N+1):
if graph[now][j] :
indegree[j] -= 1if indegree[j] == 0: # 새로 진입차수 0이 되는 노드 삽입
q.append(j)
if cycle:
print("IMPOSSIBLE")
elifnot only_one:
print("?")
else:
print(*result)