Leetcode 每日一题详解：2492. 两个城市间路径的最小分数

今天我们来刷一道 LeetCode 的题目——2492. 两个城市间路径的最小分数。这道题目看似简单，但里面藏着不少图论的陷阱和好用的思路，非常适合练手。

题目描述

题目给了一个由 n 个城市和若干条道路组成的连通图，每条道路都有一个“分数”。我们的任务是：找到城市 1 和城市 n 之间的所有路径中，那条路径上的最小道路分数中的最大值（即路径的瓶颈值最大）。换句话说，我们要找到一条从 1 到 n 的路径，使得这条路径上最小的那个道路分数是所有可能路径里最大的。

图论连通图示意图

注意：题目保证图是连通的，也就是说一定至少存在一条路径。

思路分析

这道题的核心在于如何高效地找到“瓶颈值最大”的路径。直接的想法是枚举所有可能的路径，然后计算每条路径的最小分数，最后取最大值。但这种做法的时间复杂度是指数级的，对于数据规模较大的情况显然不可行。

方法一：并查集 + 排序

并查集操作示意图

我们可以将问题转化为：在所有可能的路径中，我们要选择一条路径，使得这条路径上的最小边权重尽可能大。这可以用并查集（Union-Find）来解决。

具体步骤如下：

1. 将所有道路按照分数从大到小排序。
2. 初始化并查集，每个城市单独成一个集合。
3. 从大到小依次处理每条边。对于当前边 (u, v, score)，将 u 和 v 所在的集合合并。
4. 在合并的过程中，检查城市 1 和城市 n 是否已经连通。如果连通了，那么当前的 score 就是答案（因为我们是按分数从大到小处理的，第一次连通时的 score 就是最大可能的最小分数）。

这种方法的时间复杂度主要取决于排序，即 O(E log E)，其中 E 是边的数量。并查集的操作几乎是线性的，所以整体效率很高。

方法二：广度优先搜索（BFS）或深度优先搜索（DFS）

另一种思路是直接遍历图，记录从城市 1 出发能到达的所有城市和边。因为图是连通的，所以城市 n 一定在可达范围内。我们可以维护一个当前路径的最小分数，并在遍历过程中更新这个值。最后取所有路径中最小分数的最大值。

不过这种方法需要小心处理重复访问和路径记录的问题，不如并查集来得简洁。

代码实现

下面我们用并查集的方法来实现这道题的解法。代码是用 Python 写的，逻辑清晰，方便理解。

class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n + 1))
        self.rank = [0] * (n + 1)

def find(self, x):
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]

def union(self, x, y):
        root_x = self.find(x)
        root_y = self.find(y)
        if root_x != root_y:
            if self.rank[root_x] < self.rank[root_y]:
                self.parent[root_x] = root_y
            elif self.rank[root_x] > self.rank[root_y]:
                self.parent[root_y] = root_x
            else:
                self.parent[root_y] = root_x
                self.rank[root_x] += 1

def minScore(n, roads):
    uf = UnionFind(n)
    roads.sort(key=lambda x: -x[2])
    for u, v, score in roads:
        uf.union(u, v)
        if uf.find(1) == uf.find(n):
            return score
    return -1

代码解析

1. UnionFind 类：实现了并查集的基本操作，包括 find（查找根节点，带路径压缩）和 union（合并集合，按秩合并）。
2. minScore 函数：
   • 初始化并查集。
   • 将所有道路按分数从大到小排序。
   • 遍历每条边，合并两个端点所在的集合。
   • 每次合并后检查城市 1 和城市 n 是否已经连通。如果连通，直接返回当前边的分数。

复杂度分析

• 时间复杂度：O(E log E)，主要是排序的时间。并查集的操作可以近似看作 O(1)，所以整体时间复杂度由排序决定。
• 空间复杂度：O(n + E)，其中 n 是城市数量，E 是边的数量。并查集需要 O(n) 的空间存储父节点和秩，排序需要 O(E) 的空间（如果使用原地排序可以忽略）。

总结

这道题是并查集的一个经典应用。通过将问题转化为“在排序后的边中首次连通两个节点的分数”，我们巧妙地避免了暴力枚举所有路径的低效做法。如果你对并查集还不太熟悉，这道题绝对是一个很好的练手机会。

刷算法题不仅仅是解出答案，更重要的是掌握背后的思想。希望这篇解析对你有帮助，欢迎在评论区交流你的想法！

延伸思考

如果题目改成“两个城市间路径的最大分数的最小值”，你会怎么解呢？其实思路是一样的，只需要将边的排序顺序反过来即可。图论的题目很多都是这样，换个条件，解法可能会相似，也可能完全不同。多刷题，多思考，才能举一反三！