11631 - Dark roads

Difficulty : easy

Solution Description :

Simple Graph MST problem

This is just a Minimum Spanning Tree problem. Use Kruskal's algorithm to find the optimal solution. Using union-find to implement Kruskal is probably the easiest way.

At first total=sum of all road length. Run Kruskal algorithm and then you find minimum cost.

print (total - minimum cost)