Solution is Minimum spanning tree (Kruskal or Prim Algorithm). Put low cost on tunnels, and much higher one on bridges with using priority queue ;)

The problem is much easier. You don't need to use Kruskal or Prim to solve it.

Well, yes, but we can use this problem to train skills of writing MST algo =)

DFS!

You are trying to kill a fly with a nuclear Bomb :)

Edited by author 30.10.2019 13:44