MST - Minimum Spanning Tree
Find the minimum spanning tree of the graph.
Input
On the first line there will be two integers N - the number of nodes and M - the number of edges. (1 <= N <= 10000), (1 <= M <= 100000)
M lines follow with three integers i j k on each line representing an edge between node i and j with weight k. The IDs of the nodes are between 1 and n inclusive. The weight of each edge will be <= 1000000.
Output
Single number representing the total weight of the minimum spanning tree on this graph. There will be only one possible MST.
Example
Input: 4 5 1 2 10 2 3 15 1 3 5 4 2 2 4 3 40 Output: 17
hide comments
|
zubrach08:
2020-04-16 17:05:21
i will do it with union find
|
|
nadstratosfer:
2020-03-20 22:51:17
Probably 6 correct answers out of 11 cases (6/11 = 0.54545). |
|
master19:
2020-03-20 06:01:19
What does 54.55 indicate ??
|
|
codebreaker_00:
2020-03-05 12:07:11
O(logN)=0.57sec;
|
|
|
codebreaker_00:
2020-03-05 09:40:30
Lite
|
|
coolio_1:
2020-02-25 17:43:09
100 means you passed 100% test cases. :) |
|
hetp111:
2019-12-19 22:15:52
Time without path compression: 0.64 sec
|
|
luka_:
2019-11-14 21:07:13
nice
|
|
sajalagrawal14:
2019-08-27 01:09:40
sol:-
|
|
gourav_987:
2019-07-19 19:44:50
first time got ac in one go.100:)) |
| Added by: | Nikola P Borisov |
| Date: | 2008-10-20 |
| Time limit: | 1s-2s |
| Source limit: | 50000B |
| Memory limit: | 1536MB |
| Cluster: | Cube (Intel G860) |
| Languages: | All except: ERL JS-RHINO NODEJS PERL6 VB.NET |
RSS