Loading problem...
You are tasked with designing a network infrastructure connecting multiple data centers. There are n data centers labeled from 1 to n, and you are given a list of potential network links that can be established between them.
Each link is represented as a triplet [center₁, center₂, cost], indicating that establishing a bidirectional network connection between data center center₁ and data center center₂ requires a deployment cost of cost units.
Your objective is to determine the minimum total cost required to connect all n data centers such that there exists a communication path (direct or indirect) between every pair of data centers. In other words, all data centers must be part of a single connected network.
If it is impossible to connect all data centers using the available links (i.e., no valid spanning tree exists), return -1.
Key Observations:
n nodes requires exactly n - 1 edgesn = 3
connections = [[1,2,5],[1,3,6],[2,3,1]]6We need to connect 3 data centers. The available links are: (1→2, cost 5), (1→3, cost 6), and (2→3, cost 1). To minimize cost, we select the link (2→3, cost 1) and the link (1→2, cost 5). This gives us a total cost of 1 + 5 = 6, and all three data centers are now connected (center 1 connects to center 2, which connects to center 3).
n = 4
connections = [[1,2,3],[3,4,4]]-1We have 4 data centers but only 2 links available: (1→2, cost 3) and (3→4, cost 4). These links form two separate components: {1, 2} and {3, 4}. There is no way to connect these components together, so it's impossible to create a network spanning all 4 data centers. Hence, we return -1.
n = 4
connections = [[1,2,1],[2,3,2],[3,4,3],[1,4,4]]6We have 4 data centers and 4 potential links. To connect all 4 centers, we need exactly 3 links. The optimal selection is: (1→2, cost 1), (2→3, cost 2), and (3→4, cost 3), for a total cost of 1 + 2 + 3 = 6. Note that adding the link (1→4, cost 4) would create a cycle and is unnecessary.
Constraints