给你 Python3 版本的代码思路和之前的 Java 实现一致完整代码pythonclass Solution:def numberOfGoodPaths(self, vals: List[int], edges: List[List[int]]) - int:n len(vals)# 1. 构建邻接表graph [[] for _ in range(n)]for u, v in edges:graph[u].append(v)graph[v].append(u)# 2. 初始化并查集parent list(range(n))size [1] * ndef find(x):# 路径压缩if parent[x] ! x:parent[x] find(parent[x])return parent[x]def union(a, b):ra, rb find(a), find(b)if ra rb:returnif size[ra] size[rb]:parent[ra] rbsize[rb] size[ra]else:parent[rb] rasize[ra] size[rb]# 3. 将节点按值从小到大排序nodes sorted(range(n), keylambda x: vals[x])ans 0active [False] * n # 标记节点是否已激活值 ≤ 当前值i 0while i n:cur_val vals[nodes[i]]# 收集所有值为 cur_val 的节点cur_nodes []while i n and vals[nodes[i]] cur_val:cur_nodes.append(nodes[i])i 1# 激活当前值的节点并合并相邻的激活节点for u in cur_nodes:for v in graph[u]:if active[v]:union(u, v)active[u] True# 统计每个连通块中当前值的节点数量cnt {}for u in cur_nodes:root find(u)cnt[root] cnt.get(root, 0) 1# 计算贡献C(cnt, 2) cntfor c in cnt.values():ans c * (c 1) // 2return ans代码说明1. 核心思想· 按节点值从小到大处理· 每处理一个值 v 时只考虑值 ≤ v 的节点和边· 相同值 v 的节点如果在同一个连通块中它们之间的所有路径都是好路径2. 关键步骤· 排序节点nodes sorted(range(n), keylambda x: vals[x])· 维护 active 数组标记已经激活值 ≤ 当前值的节点· 并查集动态合并激活的节点· 统计贡献对于当前值 v在每个连通块中统计有多少个值为 v 的节点 c贡献为 c * (c 1) // 2包括长度为 0 的路径3. 时间复杂度· O(n log n m α(n))其中 m len(edges)· 排序 O(n log n)并查集操作近似 O(1)4. 空间复杂度· O(n m) 用于存图、并查集和辅助数组示例验证python# 示例 1vals [1,3,2,1,3]edges [[0,1],[0,2],[2,3],[2,4]]print(Solution().numberOfGoodPaths(vals, edges)) # 输出: 6# 示例 2vals [1,1,2,2,3]edges [[0,1],[1,2],[2,3],[2,4]]print(Solution().numberOfGoodPaths(vals, edges)) # 输出: 7
