반응형
2252번 줄 세우기
풀이
학생들의 키 비교 정보로 유향 그래프를 생성합니다. 그리고 위상정렬 알고리즘으로 풀었습니다.
import collections
v, e = map(int, input().split())
in_degree = [0] * (v+1)
graph = [[] for i in range(v+1)]
for _ in range(e):
a, b = map(int,input().split())
graph[a].append(b)
in_degree[b] += 1
result = []
q = collections.deque()
for i in range(1, v+1):
if in_degree[i] == 0:
q.append(i)
while q:
node = q.popleft()
result.append(node)
for i in graph[node]:
in_degree[i] -= 1
if in_degree[i] == 0:
q.append(i)
for i in result:
print(i, end=' ')
반응형
'Python > 백준' 카테고리의 다른 글
[백준 파이썬] 9466번 텀 프로젝트 (0) | 2021.04.20 |
---|---|
[백준 파이썬] 1707번 이분 그래프 (0) | 2021.04.19 |
[백준 파이썬] 2150번 Strongly Connected Component (5) | 2021.04.18 |
[백준 파이썬] 2606번 바이러스 (0) | 2021.04.13 |
[백준 파이썬] 1260번 DFS와 BFS (0) | 2021.04.13 |