Problem Link

https://www.hackerrank.com/contests/da-iict-ipc-02-1/challenges/mr-pompom-and-make-tunnel

Explanation :

If you make a graph such that all points on the 2d plane are connected to all other points and find the minimum spanning tree then you will get a valid answer but you can not store (10^5)^2 edges in adjacency list so you have to think about reducing the edges. There is a trick in a cost function.You want to find at least one edge for every vertex and it is minimum so we just need to consider four possibilities. First you have to sort all the points with according to x coordinate and add the edge between all the consecutive points then sort all the points according to y coordinate and add the edge between all the consecutive points.Then apply typical minimum spanning tree approach on this graph. In sorting make sure that your compare method have symmetric relation.

### Like this:

Like Loading...

Reblogged this on The Programming Club @ DA-IICT.

LikeLike