[알고리즘] 위상정렬, 프림, 크루스칼

오늘 배운 것

[알고리즘] 위상정렬, 프림, 크루스칼

거대한새 2021. 7. 12. 21:12

1. 위상정렬

https://rltn2121.tistory.com/149

백준 2252

https://www.acmicpc.net/problem/2252 2252번: 줄 세우기 첫째 줄에 N(1 ≤ N ≤ 32,000), M(1 ≤ M ≤ 100,000)이 주어진다. M은 키를 비교한 회수이다. 다음 M개의 줄에는 키를 비교한 두 학생의 번호 A, B가..

rltn2121.tistory.com

2. MST - 프림

https://rltn2121.tistory.com/150

백준 1922

https://www.acmicpc.net/problem/1922 1922번: 네트워크 연결 이 경우에 1-3, 2-3, 3-4, 4-5, 4-6을 연결하면 주어진 output이 나오게 된다. www.acmicpc.net 최소 스패닝 트리 (MST, Minimum Spanning Tree) ①..

rltn2121.tistory.com

3. MST - 크루스칼

https://rltn2121.tistory.com/151

백준 1197

https://www.acmicpc.net/problem/1197 1197번: 최소 스패닝 트리 첫째 줄에 정점의 개수 V(1 ≤ V ≤ 10,000)와 간선의 개수 E(1 ≤ E ≤ 100,000)가 주어진다. 다음 E개의 줄에는 각 간선에 대한 정보를 나타내..

rltn2121.tistory.com