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)
1#include <stdio.h>
2#include <stdlib.h>
3#include <limits.h>
4
5int find(int* parent, int i) {
6 if (parent[i] != i)
7 parent[i] = find(parent, parent[i]);
8 return parent[i];
9}
10
11void union_set(int* parent, int* rank, int x, int y) {
12 int rootX = find(parent, x);
13 int rootY = find(parent, y);
14 if (rootX != rootY) {
15 if (rank[rootX] > rank[rootY]) {
16 parent[rootY] = rootX;
17 } else if (rank[rootX] < rank[rootY]) {
18 parent[rootX] = rootY;
19 } else {
20 parent[rootY] = rootX;
21 rank[rootX]++;
22 }
23 }
24}
25
26int minScore(int n, int** roads, int roadsSize, int* roadsColSize) {
27 int* parent = (int*)malloc((n + 1) * sizeof(int));
28 int* rank = (int*)calloc(n + 1, sizeof(int));
29 for (int i = 1; i <= n; i++)
30 parent[i] = i;
31
32 int minDistance = INT_MAX;
33 for (int i = 0; i < roadsSize; i++) {
34 int a = roads[i][0];
35 int b = roads[i][1];
36 int dist = roads[i][2];
37 union_set(parent, rank, a, b);
38 }
39
40 int root1 = find(parent, 1);
41 int rootN = find(parent, n);
42
43 for (int i = 0; i < roadsSize; i++) {
44 int a = roads[i][0];
45 int b = roads[i][1];
46 int dist = roads[i][2];
47 if (find(parent, a) == root1 || find(parent, b) == root1)
48 if (dist < minDistance)
49 minDistance = dist;
50 }
51
52 free(parent);
53 free(rank);
54 return minDistance;
55}
56This solution uses a Disjoint Set Union (DSU) to identify all the cities that are connected together. It then iterates over the connections (roads), linking them up, and finally examines the edges to find the smallest possible score afterward.
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)
1import java.util.*;
2
3class Solution {
4 private int dfs(int node, boolean[] visited, Map<Integer, List<int[]>> graph, int currentMin) {
5 visited[node] = true;
6 for (int[] edge : graph.get(node)) {
7 int adj = edge[0];
8 int dist = edge[1];
9 if (!visited[adj]) {
10 currentMin = Math.min(currentMin, dist);
11 currentMin = dfs(adj, visited, graph, currentMin);
12 }
13 }
14 return currentMin;
15 }
16
17 public int minScore(int n, int[][] roads) {
18 Map<Integer, List<int[]>> graph = new HashMap<>();
19 for (int i = 1; i <= n; i++)
20 graph.put(i, new ArrayList<>());
21 for (int[] road : roads) {
22 graph.get(road[0]).add(new int[]{road[1], road[2]});
23 graph.get(road[1]).add(new int[]{road[0], road[2]});
24 }
25 boolean[] visited = new boolean[n + 1];
26 return dfs(1, visited, graph, Integer.MAX_VALUE);
27 }
28}
29Using a recursive DFS, the solution explores all nodes reachable from city 1. Graph is represented using adjacency lists stored in a map, and nodes are visited while updating the minimum edge cost encountered.