0% completed
Problem Statement
You have n
cities labeled from 1 to n
. You are given an integer n
and a list of connections where each connection is represented as [x<sub>i</sub>, y<sub>i</sub>, cost<sub>i</sub>]. This means that there is a bidirectional road between city x<sub>i</sub> and city y<sub>i</sub> with a cost of cost<sub>i</sub>.
Return the minimum cost to connect all the cities so that there is a path between any two cities. If it's not possible to connect all cities, return -1
. The total cost is the sum of the costs of the connections used.
Examples
-
Example 1:
- Input: n = 5, connections = [[1, 2, 2], [1, 3, 3], [4, 5, 1], [3, 4, 4], [2, 5, 6]]
- Expected Output: 10
- Explanation: The minimum cost to connect all cities is obtained by using the connections
[1, 2, 2]
,[1, 3, 3]
,[4, 5, 1]
, and[3, 4, 4]
. This gives a total cost of2 + 3 + 1 + 4 = 10
.
-
Example 2:
- Input: n = 4, connections = [[1, 2, 3], [2, 3, 4], [3, 4, 5], [1, 4, 10]]
- Expected Output: 12
- Explanation: The minimum cost to connect all cities is obtained by using the connections
[1, 2, 3]
,[2, 3, 4]
, and[3, 4, 5]
. This gives a total cost of3 + 4 + 5 = 12
.
-
Example 3:
- Input: n = 3, connections = [[1, 2, 6], [2, 3, 2], [1, 3, 10]]
- Expected Output: 8
- Explanation: The minimum cost to connect all cities is obtained by using the connections
[1, 2, 6]
and[2, 3, 2]
. This gives a total cost of6 + 2 = 8
.
Constraints:
- 1 <= n <= 10<sup>4</sup>
- 1 <= connections.length <= 10<sup>4</sup>
- connections[i].length == 3
- 1 <= x<sub>i</sub>, y<sub>i</sub> <= n
- x<sub>i</sub> != y<sub>i</sub>
- 0 <= cost<sub>i</sub> <= 10<sup>5</sup>
Solution
To solve this problem, we will use Kruskal's algorithm. This algorithm is ideal for finding the Minimum Spanning Tree (MST) in a graph. The MST ensures all nodes are connected with the least total cost, which suits our requirement to connect all cities with the minimum cost.
Kruskal's algorithm works by sorting all edges in ascending order of their weight and then adding edges one by one to the MST. We use the Union-Find data structure to check if adding an edge will form a cycle. If it does not form a cycle, we add it to our MST. This process continues until all cities are connected or we have examined all edges.
Step-by-Step Algorithm
-
Initialize Union-Find Structure:
- Create a
UnionFind
class to manage the connected components. - This class should have methods to find the root of a node and to unite two components.
- Create a
-
Convert and Sort Edges:
- Convert the list of connections to a list of edges, adjusting the city indices to be zero-based.
- Sort the edges by their cost in ascending order.
-
Initialize Variables:
- Create a variable
totalCost
to keep track of the total cost of connecting the cities. - Create a variable
edgesUsed
to count the number of edges used in the minimum spanning tree.
- Create a variable
-
Process Each Edge:
- Iterate through the sorted edges.
- For each edge, use the
union
method to attempt to connect the two cities.- If the cities were not already connected, add the cost of the edge to
totalCost
and incrementedgesUsed
. - If
edgesUsed
equalsn - 1
, returntotalCost
as we have connected all cities.
- If the cities were not already connected, add the cost of the edge to
-
Check Connectivity:
- If after processing all edges,
edgesUsed
is less thann - 1
, return-1
because it's not possible to connect all cities.
- If after processing all edges,
Algorithm Walkthrough
Using the input:
n = 5
connections = [[1, 2, 2], [1, 3, 3], [4, 5, 1], [3, 4, 4], [2, 5, 6]]
-
Convert and Sort Edges:
- Adjust connections to be zero-based:
[(0, 1, 2), (0, 2, 3), (3, 4, 1), (2, 3, 4), (1, 4, 6)]
- Sort by cost:
[(3, 4, 1), (0, 1, 2), (0, 2, 3), (2, 3, 4), (1, 4, 6)]
- Adjust connections to be zero-based:
-
Initialize Union-Find:
parent = [0, 1, 2, 3, 4]
rank = [0, 0, 0, 0, 0]
totalCost = 0
edgesUsed = 0
-
Process First Edge
(3, 4, 1)
:find(3)
returns3
find(4)
returns4
union(3, 4)
:- Union successful
parent = [0, 1, 2, 3, 3]
rank = [0, 0, 0, 1, 0]
totalCost += 1
→totalCost = 1
edgesUsed += 1
→edgesUsed = 1
-
Process Second Edge
(0, 1, 2)
:find(0)
returns0
find(1)
returns1
union(0, 1)
:- Union successful
parent = [0, 0, 2, 3, 3]
rank = [1, 0, 0, 1, 0]
totalCost += 2
→totalCost = 3
edgesUsed += 1
→edgesUsed = 2
-
Process Third Edge
(0, 2, 3)
:find(0)
returns0
find(2)
returns2
union(0, 2)
:- Union successful
parent = [0, 0, 0, 3, 3]
rank = [1, 0, 0, 1, 0]
totalCost += 3
→totalCost = 6
edgesUsed += 1
→edgesUsed = 3
-
Process Fourth Edge
(2, 3, 4)
:find(2)
returns0
find(3)
returns3
union(0, 3)
:- Union successful
parent = [0, 0, 0, 0, 3]
rank = [2, 0, 0, 1, 0]
totalCost += 4
→totalCost = 10
edgesUsed += 1
→edgesUsed = 4
-
Check if All Cities are Connected:
edgesUsed = 4
equalsn - 1 = 4
- All cities are connected, return
totalCost = 10
Thus, the minimum cost to connect all the cities is 10
.
Code
Complexity Analysis
-
Time Complexity:
- Sorting Edges: Sorting the edges based on their cost takes O(E \log E), where (E) is the number of edges.
- Union-Find Operations: The union-find operations (find and union) take almost constant time, O(\alpha(N)), where \alpha\ is the inverse Ackermann function. Thus, for (E) edges, it will be O(E \alpha(N)).
- Total Time Complexity: Combining these, the total time complexity is O(E \log E + E \alpha(N)). Since \alpha(N) is very small and can be considered nearly constant, the time complexity is dominated by O(E \log E).
-
Space Complexity:
- Union-Find Data Structures: Storing the parent and rank arrays takes O(N) space, where (N) is the number of cities.
- Edge List: Storing the edges requires O(E) space.
- Total Space Complexity: The total space complexity is O(N + E).
.....
.....
.....
Table of Contents
Contents are not accessible
Contents are not accessible
Contents are not accessible
Contents are not accessible
Contents are not accessible