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)
1public class Solution {
2 public class UnionFind {
3 public int[] parent, rank;
4 public UnionFind(int n) {
5 parent = new int[n + 1];
6 rank = new int[n + 1];
7 for (int i = 1; i <= n; i++)
8 parent[i] = i;
9 }
10
11 public int Find(int u) {
12 if (parent[u] != u)
13 parent[u] = Find(parent[u]);
14 return parent[u];
15 }
16
17 public void Union(int u, int v) {
18 int pu = Find(u);
19 int pv = Find(v);
20 if (pu != pv) {
21 if (rank[pu] > rank[pv])
22 parent[pv] = pu;
23 else if (rank[pu] < rank[pv])
24 parent[pu] = pv;
25 else {
26 parent[pv] = pu;
27 rank[pu]++;
28 }
29 }
30 }
31 }
32
33 public int MinScore(int n, int[][] roads) {
34 UnionFind uf = new UnionFind(n);
35 int result = int.MaxValue;
36 foreach (int[] road in roads) {
37 uf.Union(road[0], road[1]);
38 }
39 foreach (int[] road in roads) {
40 if (uf.Find(road[0]) == uf.Find(1) || uf.Find(road[1]) == uf.Find(1))
41 result = Math.Min(result, road[2]);
42 }
43 return result;
44 }
45}
46This C# solution constructs a Union-Find data structure to unite the roads, and then it scans through connected roads to find the minimal score for connecting city 1 to city n.
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)
1#include <stdio.h>
2#include <stdlib.h>
3#include <limits.h>
4#include <stdbool.h>
5
6int graph[100001][101], edge[100001][101];
7int g_size[100001];
8bool visited[100001];
9
10int minScoreDFS(int node, int minEdge, int n) {
11 visited[node] = true;
12 for (int i = 0; i < g_size[node]; i++) {
13 int adjacent = graph[node][i];
14 int dist = edge[node][i];
15 if (!visited[adjacent]) {
16 minEdge = minEdge < dist ? minEdge : dist;
17 minEdge = minScoreDFS(adjacent, minEdge, n);
18 }
19 }
20 return minEdge;
21}
22
23int minScore(int n, int** roads, int roadsSize, int* roadsColSize) {
24 for (int i = 1; i <= n; i++) {
25 visited[i] = false;
26 g_size[i] = 0;
27 }
28
29 for (int i = 0; i < roadsSize; i++) {
30 int a = roads[i][0];
31 int b = roads[i][1];
32 int d = roads[i][2];
33 graph[a][g_size[a]] = b;
34 edge[a][g_size[a]++] = d;
35 graph[b][g_size[b]] = a;
36 edge[b][g_size[b]++] = d;
37 }
38
39 return minScoreDFS(1, INT_MAX, n);
40}
41This C code uses DFS with an array of lists to store adjacent nodes. During DFS traversal, it keeps track of the minimum-weight edge to ensure the minimum score path is calculated.