2024 Algorithm

From: 2024-03-01 00:00:00 To: 2024-12-31 00:00:00 Now: 2024-11-21 22:35:19 Status: Public

D - Minimum Spanning Tree (Prim's algorithm)

Time Limit: 1s Memory Limit: 128MB

Submissions: 585 Solved: 117

Description

주어진 connected/weighted/undirected graph의 minimum spanning tree (MST)를 구하는 Prim's algorithm 기반의 코드를 작성하시오.

* Each vertex will be assigned an index from 0 to n-1 (n =number of vertices). Prim's algorithm must be executed with the first vertex as the root vertex (r = v₀).

* For r = v₀, all test case graphs will have one unique MST.

* Sample Input/Output은 Figure 21.4의 그래프를 예시로 함 (단, r = a일때 하나의 답만 나오도록 edge <a,h>는 삭제함)

Input

- Line 0: n

- Line 1: m

- Line 2~m+1: edges in random order where each edge is represented as (vertex index a, vertex index b, integer weight w)

* n = number of vertices in graph

* m = number of edges in graph

Output

- Line 0: (vertex index of) parent of v₁in MST

...

- Line n-2: (vertex index of) parent of v_n-1in MST

Sample Input

9
13
0,1,4
1,7,11
1,2,8
2,8,2
2,3,7
2,5,4
8,7,7
8,6,6
7,6,1
6,5,2
3,5,14
3,4,9
4,5,10

Sample Output