Lab 2

You cannot submit for this problem because the homework's deadline is due.

Description

Implement Kruskal and Prim's algorithm for solving the minimum spanning tree.
If you find any error or bug related to this problem, email me via lnyq10@sjtu.edu.cn.

Format

You should use a Makefile that compiles your source file into an executeable file named "main".

Input

number of edges \(eSize\) on the first line
number of vertexes \(vSize\) on the second line
an edge in the form "\(v1\) \(v2\) \(w\)" on the following \(eSize\) line
\(v1\) and \(v2\) are the indexes (start at 0) of the two vertexes of the edge
\(w\) is the weight of the edge

Output

All the edges in the resulting minimum spanning tree
Print all the edges in the format
"\(v1\)--\(v2\)"
\(v1\) and \(v2\) are the indexes of the two vertexes of the edge, \(v1\) < \(v2\)
Print all edges in the increasing order of \(v1\), for two edges "\(v1\) \(v2\)" and
"\(v1\) \(v3\)" with \(v2\) < \(v3\), print "\(v1\) \(v2\)" first.

Sample 1

Input

5
4
0 1 1
1 2 2
2 3 3
3 0 2
0 2 5

Output

0--1
0--3
1--2

Hints

  1. Case 5 is exactly the sample case
  2. Case 1 is given as

Lab 2

Not Claimed
Status
Finished
Problems
1
Open Since
2019-09-20 00:00
DDL
2019-09-27 23:59
Extension
24.0 hour(s)