This approach involves using the Union-Find data structure (also known as Disjoint Set Union, DSU) to manage connections between cities efficiently. By iterating over all roads, we determine which cities are interconnected. The key is to keep track of the minimum weight of a road that connects these cities after they are all unified.
This solution utilizes an efficient means of finding and unifying elements, reducing the overhead of nested loops and allowing operations near constant-time with path compression and union by rank techniques.
Time Complexity: O(E log* V)
Space Complexity: O(V)
1class UnionFind:
2 def __init__(self, n):
3 self.parent = list(range(n + 1))
4 self.rank = [0] * (n + 1)
5
6 def find(self, u):
7 if self.parent[u] != u:
8 self.parent[u] = self.find(self.parent[u])
9 return self.parent[u]
10
11 def union(self, u, v):
12 pu = self.find(u)
13 pv = self.find(v)
14 if pu != pv:
15 if self.rank[pu] > self.rank[pv]:
16 self.parent[pv] = pu
17 elif self.rank[pu] < self.rank[pv]:
18 self.parent[pu] = pv
19 else:
20 self.parent[pv] = pu
21 self.rank[pu] += 1
22
23def minScore(n, roads):
24 uf = UnionFind(n)
25 result = float('inf')
26
27 for a, b, dist in roads:
28 uf.union(a, b)
29
30 for a, b, dist in roads:
31 if uf.find(a) == uf.find(1) or uf.find(b) == uf.find(1):
32 result = min(result, dist)
33
34 return result
35Python implementation leverages a Union-Find class to efficiently deal with interconnected components and keeps track of the minimal distance of roads connecting city 1 with other connected cities.
Another intuitive approach is to use graph traversal techniques such as BFS or DFS. Starting from city 1, you can explore all reachable cities while dynamically updating the minimum edge encountered during the exploration. This ensures you calculate the smallest score path by evaluating all potential paths to the destination city.
Time Complexity: O(V + E)
Space Complexity: O(V + E)
1using System;
2using System.Collections.Generic;
3
4public class Solution {
5 private int DFS(int node, bool[] visited, Dictionary<int, List<int[]>> graph, int currentMin) {
6 visited[node] = true;
7 foreach (var edge in graph[node]) {
8 int adj = edge[0];
9 int dist = edge[1];
10 if (!visited[adj]) {
11 currentMin = Math.Min(currentMin, dist);
12 currentMin = DFS(adj, visited, graph, currentMin);
13 }
14 }
15 return currentMin;
16 }
17
18 public int MinScore(int n, int[][] roads) {
19 var graph = new Dictionary<int, List<int[]>>();
20 for (int i = 1; i <= n; i++)
21 graph[i] = new List<int[]>();
22 foreach (var road in roads) {
23 graph[road[0]].Add(new int[]{road[1], road[2]});
24 graph[road[1]].Add(new int[]{road[0], road[2]});
25 }
26 var visited = new bool[n + 1];
27 return DFS(1, visited, graph, int.MaxValue);
28 }
29}
30The C# DFS approach uses a Dictionary to create an adjacency list of cities and applies depth-first search starting from city 1 to find and track the smallest valid connecting edge to city n.