문제
풀이
위상 정렬에 대한 문제이다. 해당 index보다 뒷순위에 해당하는 것들이 담긴 인접 리스트와 뒤에 몇명이 있는지를 나타내는 degree배열을 선언해준다.
예를 들어, 5 4 3 2 1 순위라면 5 -> 4, 3, 2, 1 // 4 -> 3, 2, 1 // 3 -> 2, 1 … 이런식이다.
바뀐 값이 나오면 인접 리스트를 수정해주고, degree 배열의 값을 update해준다.
위상 정렬을 진행하기 위해 queue에 넣는데, impossible되는 경우는 초기에 q에 아무 것도 안들어가는 경우, 또 들어가더라도, 한번에 2개 이상이 들어가는 경우(degree값이 같은 경우), 혹은 degree값이 음수가 되는 경우이다.
또, 결과를 담은 리스트에 기존의 팀 수 만큼 담기지 않았다면 이상하다는 것이므로 impossble을 출력한다.
작년에 확실한 순위가 정해져있기 때문에 확실한 순위를 찾을 수 없는 경우는 없다.
Reference를 참조하였다.
소스 코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
import sys
import collections as cl
from math import *
testcase = int(sys.stdin.readline())
for _ in range(testcase):
n = int(sys.stdin.readline())
rank = list(map(int, sys.stdin.readline().split()))
vector = [[] for _ in range(n+1)]
#간선 생성
degree = [0 for _ in range(n+1)]
for i in range(n-1):
for j in range(i+1, n):
vector[rank[i]].append(rank[j])
degree[rank[j]] += 1
# 인접리스트 작성, 뒤에 몇명 있는지 나타내는 degree 배열
m = int(sys.stdin.readline())
for _ in range(m):
a, b = map(int, sys.stdin.readline().split())
check = True
for i in vector[a]:
if i == b:
vector[a].remove(b)
vector[b].append(a)
degree[a] += 1
degree[b] -= 1
check = False
if(check):
vector[b].remove(a)
vector[a].append(b)
degree[b] += 1
degree[a] -= 1
# 바뀌는 것을 반영
q = cl.deque()
for i in range(1, n+1):
if degree[i] == 0:
q.append(i)
# 0인것 삽입
result = True
result_list = []
if not q: #q에 아무것도 들어가 있지 않다면...
result = False
while q:
if len(q)>1: #q에 한번에 두개이상이 들어가 있다면...
result = False
print(1)
break
current = q.popleft()
result_list.append(current)
for i in vector[current]:
degree[i] -= 1
if degree[i] == 0:
q.append(i)
elif degree[i] < 0:
result = False
print(2)
break
if(result == False or len(result_list) < n):
print("IMPOSSIBLE")
else:
print(*result_list)
