Minimum Score of a Path Between Two Cities
Medium · Graphs · Explanation and code example
Disjoint Set Union
How it works
Union-Find provides another way to identify which edges belong to the same connected component as node 1. First, we union all nodes connected by edges. Then, we iterate through all edges and check if they belong to the same component as node 1. The minimum weight among those edges is our answer.
Steps
- Initialize a DSU (Disjoint Set Union) structure with path compression and union by size.
- For each edge, union the two endpoints.
- Find the root of node
1. - Iterate through all edges:
- If either endpoint has the same root as node
1, updatereswith the minimum edge weight.
- If either endpoint has the same root as node
- Return
res.
Complexity
- Time complexity:
O(V + (E * α(V))) - Space complexity:
O(V)
Where
Vis the number of vertices andEis the number of edges in the graph.α()is used for amortized complexity.
Things to watch for
Treating It as a Shortest Path Problem
Many people instinctively reach for Dijkstra's algorithm when they see "minimum" and "path" in the same problem. However, this problem asks for the minimum edge weight along any path, not the shortest total distance. Since you can revisit edges freely, you simply need to find the smallest edge weight in the entire connected component containing node 1.
Only Considering Direct Paths
Some solutions only examine edges that lie on simple paths from node 1 to node n. This misses the key insight that you can traverse any edge in the connected component by taking detours. The answer is the minimum weight among all edges reachable from node 1, regardless of whether they appear on a direct path to node n.
Forgetting to Build Bidirectional Edges
The graph is undirected, so each edge must be added in both directions when constructing the adjacency list. Failing to do this will cause your traversal to miss large portions of the graph, leading to incorrect results when the minimum edge is only reachable through a path that requires traversing an edge in the "reverse" direction.
Python code example
class DSU:
def __init__(self, n):
self.Parent = list(range(n + 1))
self.Size = [1] * (n + 1)
def find(self, node):
if self.Parent[node] != node:
self.Parent[node] = self.find(self.Parent[node])
return self.Parent[node]
def union(self, u, v):
pu, pv = self.find(u), self.find(v)
if pu == pv:
return False
if self.Size[pu] >= self.Size[pv]:
self.Size[pu] += self.Size[pv]
self.Parent[pv] = pu
else:
self.Size[pv] += self.Size[pu]
self.Parent[pu] = pv
return True
class Solution:
def minScore(self, n: int, roads: list[list[int]]) -> int:
dsu = DSU(n)
for src, dst, _ in roads:
dsu.union(src, dst)
res = float("inf")
root = dsu.find(1)
for src, dst, dist in roads:
if dsu.find(src) == root:
res = min(res, dist)
return res
C++ code example
class DSU {
public:
vector<int> parent, size;
DSU(int n) {
parent.resize(n + 1);
size.resize(n + 1, 1);
for (int i = 0; i <= n; i++) {
parent[i] = i;
}
}
int find(int node) {
if (parent[node] != node) {
parent[node] = find(parent[node]);
}
return parent[node];
}
bool unionSets(int u, int v) {
int pu = find(u), pv = find(v);
if (pu == pv) return false;
if (size[pu] >= size[pv]) {
size[pu] += size[pv];
parent[pv] = pu;
} else {
size[pv] += size[pu];
parent[pu] = pv;
}
return true;
}
};
class Solution {
public:
int minScore(int n, vector<vector<int>>& roads) {
DSU dsu(n);
for (auto& road : roads) {
dsu.unionSets(road[0], road[1]);
}
int res = INT_MAX;
int root = dsu.find(1);
for (auto& road : roads) {
if (dsu.find(road[0]) == root) {
res = min(res, road[2]);
}
}
return res;
}
};
Source and license
Adapted from NeetCode’s source · MIT license. Node types are supplied by LeetCode where needed.