https://www.acmicpc.net/problem/2623
시간 1초, 메모리 128MB
input :
- N M
- 담당 가수의 수, 가수의 순서
output :
- 남일이가 정한 가수들의 출연 순서를 나타낸다. 답이 여럿일 경우에는 아무거나 하나를 출력 한다.
- 순서를 정하는 것이 불가능할 경우에는 첫째 줄에 0을 출력
조건 :
- 남일이가 할 일은 이 순서들을 모아서 전체 가수의 순서를 정하는 것이다.
- [6 2 1 5 4 3] or [1 6 2 5 4 3]
- 이렇게 가수 순서를 정하면 세 보조 PD가 정해온 순서를 모두 만족한다.
idea
주의
모든 노드를 확인했는지를 판별해야 한다. 이를 위해선 차수의 합을 계산하는 것이 제일 편할 것 같다.
import sys
from collections import deque
n, m = map(int, sys.stdin.readline().split())
node, graph = [0] * (n + 1), [[] for _ in range(n + 1)]
for _ in range(m):
edge = list(map(int, sys.stdin.readline().split()))[1:]
for idx in range(len(edge) - 1):
now, daum = edge[idx], edge[idx + 1]
graph[now].append(daum)
node[daum] += 1
q = deque([])
for i in range(1, n + 1):
if node[i] == 0:
q.append(i)
ans = []
while q:
now = q.popleft()
ans.append(now)
for next_node in graph[now]:
node[next_node] -= 1
if node[next_node] == 0:
q.append(next_node)
if sum(node) != 0:
print(0)
exit(0)
for item in ans:
print(item)
