1) An element of the ‘COORDINATES’ array is a pair of ‘X' and ‘Y’ coordinates of a point, i.e., COORDINATES[i] = (Xi, Yi). 2) |DISTANCE| represents the absolute value of distance. 3) All points are considered to be connected if there is exactly one simple path between two points. 4) According to Wikipedia, a simple path is a path in a plane that does not have repeating points.
The first line of input contains an integer 'T' representing the number of test cases. The first line of each test case contains an integer ‘N’ representing the number of points in the ‘COORDINATES’ array. The next ‘N’ lines of each test case contain two space-separated integers representing the ‘X and ‘Y’ coordinates of a point.
For each test case, print a single line containing a single integer denoting the minimum cost to make all the points connected. The output of each test case will be printed in a separate line.
You do not need to print anything, it has already been taken care of. Just implement the given function.
1 <= T <= 5 1 <= N <= 1000 10 ^ -6 <= X, Y <= 10 ^ 6 All points are distinct. Where ‘T’ is the number of test cases, ‘N’ is the number of points in the ‘COORDINATES’ array, ‘X’, ‘Y’ is the x and y coordinates of a point, respectively. Time limit: 1 sec.
The problem indirectly refers to finding the cost of the minimum spanning tree of the graph formed by given points.
By definition, a minimum spanning tree (MST) is a subset of the edges of a connected, edge-weighted undirected graph that connects all the vertices, without any cycles and with the minimum possible total edge weight. For ‘n’ vertices, an MST has ‘n - 1’ edges.
The idea is to use Kruskal’s Algorithm to find the MST for this problem.
First, we will add all the edges (that can be formed by any two points) and their cost in a min-heap. Now, we will process each and every edge present in the min-heap one by one. Min heap ensures that edges are processed in non-decreasing order of their cost.
If the current edge in processing forms a cycle in the MST, then discard the edge; otherwise, include it in the MST. We will be adding the cost of edges included in the MST in an integer variable, ‘result’.
The process will be repeated till ‘n - 1’ edges are not included in the MST, where ‘n’ is the number of points in the ‘coordinates’ array. In the end, the ‘result’ will have the cost of MST so formed.
Description of ‘DisjointSet’ class
The private part of the ‘DisjointSet’ class will contain two data members:
The private part of the ‘DisjointSet’ class will contain one constructor and two member functions:
Description of ‘DisjointSet’ constructor
The constructor will take one parameter:
Description of ‘find’ function
The function will take one parameter:
Description of ‘Union’ function
The function will take two parameters: