[백준] 1766 문제집 - 파이썬

풀이.

진입 차수가 0인 정점을 힙에 삽입하고 힙에서 해당 원소를 꺼내고 해당 원소와 연결된 간선을 제거해준다

이후 진입 차수가 0이된 정점을 힙에 삽입을하고 힙이 모두 빌 때까지 반복을 한다.

 

소스코드.

 

	import heapq
	import sys
	def topology():
	heap = []
	result = []
	for i in range(1, n+1):
	if indegree[i] == 0:
	heapq.heappush(heap, i)
	while heap:
	score = heapq.heappop(heap)
	result.append(score)
	for y in arr[score]:
	indegree[y] -= 1
	if indegree[y] == 0:
	heapq.heappush(heap, y)
	return result
	input = sys.stdin.readline
	n, m = map(int, input().split())
	arr = [[] for i in range(n+1)]
	indegree = [0] * (n+1)
	for i in range(m):
	x, y = map(int, input().split())
	arr[x].append(y)
	indegree[y] += 1
	print(*topology())

view raw 1766 - 문제집.py hosted with ❤ by GitHub