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)
1import java.util.*;
2
3class Solution {
4 class UnionFind {
5 int[] parent, rank;
6
7 UnionFind(int n) {
8 parent = new int[n + 1];
9 rank = new int[n + 1];
10 for (int i = 1; i <= n; i++)
11 parent[i] = i;
12 }
13
14 int find(int u) {
15 if (parent[u] != u)
16 parent[u] = find(parent[u]);
17 return parent[u];
18 }
19
20 void union(int u, int v) {
21 int pu = find(u);
22 int pv = find(v);
23 if (pu != pv) {
24 if (rank[pu] > rank[pv])
25 parent[pv] = pu;
26 else if (rank[pu] < rank[pv])
27 parent[pu] = pv;
28 else {
29 parent[pv] = pu;
30 rank[pu]++;
31 }
32 }
33 }
34 }
35
36 public int minScore(int n, int[][] roads) {
37 UnionFind uf = new UnionFind(n);
38 int result = Integer.MAX_VALUE;
39 for (int[] road : roads) {
40 int a = road[0], b = road[1];
41 uf.union(a, b);
42 }
43
44 for (int[] road : roads) {
45 if (uf.find(road[0]) == uf.find(1) || uf.find(road[1]) == uf.find(1))
46 result = Math.min(result, road[2]);
47 }
48
49 return result;
50 }
51}
52The algorithm uses a Union-Find data structure to connect all the cities and iteratively examines each connecting road to calculate the minimum possible score after all the interconnections are established.
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)
1function minScore(n, roads) {
2 const graph = Array.from({ length: n + 1 }, () => []);
3
4 for (const [a, b, dist] of roads) {
5 graph[a].push([b, dist]);
6 graph[b].push([a, dist]);
7 }
8
9 const visited = new Array(n + 1).fill(false);
10
11 function dfs(node, currentMin) {
12 visited[node] = true;
13 for (const [adj, dist] of graph[node]) {
14 if (!visited[adj]) {
15 currentMin = Math.min(currentMin, dist);
16 currentMin = dfs(adj, currentMin);
17 }
18 }
19 return currentMin;
20 }
21
22 return dfs(1, Infinity);
23}
24An adjacency list implemented using arrays allows for DFS traversal from city 1, iterating on the edges to locate and maintain the minimum road weight for paths including city n.