Minimum cost to connect cities

Given a city network having A nodes. The Roads of this city are damaged and you are asked to repair the roads.

Given a matrix B of size M x 3 which represents the road such that there is a road between
B[i][0] and B[i][1] before the damage and cost of repairing this road is B[i][2].
you need to repair some of the roads with the minimum cost such that the city will get connected after repairing the roads.
In other words, after repairing some of the the roads, every pair of the city will be reachable from one another.

Note:

  1. No city was connected to itself before the roads were damaged.

  2. Before the damage of roads, there is only one road between the given pair of roads.

  3. Cities are Numbered from 1 to A.

  4. The city network is connected before the roads are damaged.

  5. Your solution will run on multiple test cases. If you are using global variables make sure to clear them.



Input Format

The first argument given is an integer A.
The second argument given is the matrix B.

Output Format

Return the minimum cost to repair some of the the roads so that the city will get connected.

Constraints

1 <= A <= 100000
1 <= M <= min(100000, (A*(A-1)/2))
1 <= B[i][0], B[i][1] <= A
0 <= B[i][2] <= 10000;

For Example

Input 1:
    A = 5
    B = [   [2, 1, 3]
            [2, 3, 5] 
            [3, 5, 1] 
            [1, 4, 9] 
            [5, 4, 5] 
            [5, 2, 3] 
            [5, 1, 2] 
            [4, 3, 10] ] 
Output 1:
    11

Input 2:
    A = 8
    B = [   [4, 3, 8]
            [3, 2, 6] 
            [2, 7, 9] 
            [7, 5, 2] 
            [5, 6, 10] 
            [7, 8, 1] 
            [4, 1, 2] 
            [8, 6, 2] ]
Output 2:
    30
NOTE: You only need to implement the given function. Do not read input, instead use the arguments to the function. Do not print the output, instead return values as specified. Still have a doubt? Checkout Sample Codes for more details.
Start solving Minimum cost to connect cities on Interview Code Editor
Sign Up
to access hints and editorial solutions for Minimum cost to connect cities

Discussion


Loading...
Click here to start solving coding interview questions