TopologySort

·Algorithm (PS)
위상 정렬만 알면 날먹 가능한 문제이다 https://www.acmicpc.net/problem/2252 학생들을 줄 세워야 하는데 우선순위의 일부분이 m개 주어진다 이를 위상정렬 그래프로 생각하면 반드시 정점 a(학생1) 을 먼저 방문한 이후, 정점 b(학생2) 를 방문해야 한다 라는 순서가 된다. 위상정렬에서는 정점 b를 가기 위해서는 반드시 정점 a를 지나쳐야 하므로, 진입차수(indegree)가 1 증가하게 된다. # 위상 정렬 from collections import deque v, e = map(int, input().split()) indegree = [0]*(v+1) # 진입 차수 graph = [[] for _ in range(v+1)] for _ in range(e): a, b = m..
minjiwoo
'TopologySort' 태그의 글 목록