아무 말

https://www.acmicpc.net/problem/2252 2252번: 줄 세우기 첫째 줄에 N(1 ≤ N ≤ 32,000), M(1 ≤ M ≤ 100,000)이 주어진다. M은 키를 비교한 회수이다. 다음 M개의 줄에는 키를 비교한 두 학생의 번호 A, B가 주어진다. 이는 학생 A가 학생 B의 앞에 서야 한다는 의 www.acmicpc.net 심플하게 위상 정렬을 수행하는 문제 위상 정렬에 대한 설명은 아래의 포스트를 참조 https://jiuge-meogari-ps.tistory.com/14 위상 정렬(Topological Sort) 위상 정렬(topological sort)은 G가 간선 (u,v)를 가질 때 u가 v보다 순서상으로 먼저 나타나도록 모든 정점을 선형으로 나열하는 것이다. 여기..

위상 정렬(topological sort)은 G가 간선 (u,v)를 가질 때 u가 v보다 순서상으로 먼저 나타나도록 모든 정점을 선형으로 나열하는 것이다. 여기서 만약 그래프가 순환을 가진다면 선형 나열은 불가능하다. 아래와 같은 알고리즘은 하나의 방향 비순환 그래프를 위상 정렬 한다. 위상 정렬(G) 1 각 정점 v에 대해 종료 시간 v.f를 계산하기 위해 DFS(G)를 호출한다. 2 각 정점이 종료될 때마다 연결 리스트의 맨 앞에 삽입한다. 3 return 정점의 연결 리스트 중요한것은 위상 정렬한 순서대로 일을 수행할 때 일을 수행하지 못하는 일이 나오지 않는다는 것이다. 미리 어떠한 행동 A를 해야 B를 할 수 있다면 A를 하고 B를 해야한다는 것이다. 위 방식으로 위상 정렬을 할 때 시간복잡도는..