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 constructor(n) {
3 this.parent = Array.from({length: n + 1}, (_, i) => i);
4 this.rank = Array(n + 1).fill(0);
5 }
6
7 find(u) {
8 if (this.parent[u] !== u) {
9 this.parent[u] = this.find(this.parent[u]);
10 }
11 return this.parent[u];
12 }
13
14 union(u, v) {
15 let pu = this.find(u);
16 let pv = this.find(v);
17 if (pu !== pv) {
18 if (this.rank[pu] > this.rank[pv]) {
19 this.parent[pv] = pu;
20 } else if (this.rank[pu] < this.rank[pv]) {
21 this.parent[pu] = pv;
22 } else {
23 this.parent[pv] = pu;
24 this.rank[pu]++;
25 }
26 }
27 }
28}
29
30function minScore(n, roads) {
31 const uf = new UnionFind(n);
32 let result = Infinity;
33 for (const [a, b, dist] of roads) {
34 uf.union(a, b);
35 }
36 for (const [a, b, dist] of roads) {
37 if (uf.find(a) === uf.find(1) || uf.find(b) === uf.find(1)) {
38 result = Math.min(result, dist);
39 }
40 }
41 return result;
42}
43This JavaScript solution defines a Union-Find class and uses it to connect nodes, analyzing roads that provide connectivity to maintain the smallest possible score.
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)
1def minScore(n, roads):
2 from collections import defaultdict
3 graph = defaultdict(list)
4
5 for a, b, dist in roads:
6 graph[a].append((b, dist))
7 graph[b].append((a, dist))
8
9 def dfs(node, visited, currentMin):
10 visited[node] = True
11 for adj, dist in graph[node]:
12 if not visited[adj]:
13 currentMin = min(currentMin, dist)
14 currentMin = dfs(adj, visited, currentMin)
15 return currentMin
16
17 visited = [False] * (n + 1)
18 return dfs(1, visited, float('inf'))
19Python implementation captures the graph using a dictionary of lists. Using DFS starting from node 1, it identifies and updates the lowest edge score to connect to city n.