Kimi LeetCode 3547. 图中边值的最大和 Python3实现

以下是 LeetCode 3547. 图中边值的最大和 的 Python3 实现。解题思路由于每个节点最多与其他两个节点相连整个图由若干链和环组成。1. 连通分量分类用 DFS/BFS 找出所有连通分量。若分量内所有节点度数均为 2则为环否则为链孤立点不贡献边权忽略。2. 处理顺序先处理环每个节点有两条边大数在环中能产生更多乘积再处理链按长度降序长链优先拿大数。3. 填数策略将剩余的最大数放在连通分量中间次大数交替向两边扩展使得大数尽量相邻双端队列模拟。时间复杂度 O(n \log n)空间复杂度 O(n)。---Python3 代码pythonfrom collections import dequefrom typing import Listclass Solution:def maxScore(self, n: int, edges: List[List[int]]) - int:# 建图graph [[] for _ in range(n)]for u, v in edges:graph[u].append(v)graph[v].append(u)seen [False] * ncycle_sizes [] # 环的大小path_sizes [] # 链的大小# 遍历每个连通分量for i in range(n):if seen[i]:continue# DFS 收集连通分量component []stack [i]seen[i] Truewhile stack:u stack.pop()component.append(u)for v in graph[u]:if not seen[v]:seen[v] Truestack.append(v)# 判断是否为环所有节点度数均为 2is_cycle Truefor u in component:if len(graph[u]) ! 2:is_cycle Falsebreakif is_cycle:cycle_sizes.append(len(component))elif len(component) 1:path_sizes.append(len(component))# 孤立点size 1不贡献边权无需处理ans 0# 先处理环从剩余的最大数中分配for size in cycle_sizes:ans self._calc_score(n - size 1, n, True)n - size# 链按长度从大到小排序优先处理长链path_sizes.sort(reverseTrue)for size in path_sizes:ans self._calc_score(n - size 1, n, False)n - sizereturn ansdef _calc_score(self, left: int, right: int, is_cycle: bool) - int:将 [left, right] 范围内的数填入一个连通分量计算最大边权和。策略双端队列模拟中间放大数向两边递减的排列。初始放入两个 right从 right-1 递减到 left每次取出队首与当前值相乘再将当前值放入队尾。dq deque()dq.append(right)dq.append(right)score 0for val in range(right - 1, left - 1, -1):window_val dq.popleft()score window_val * valdq.append(val)# 如果是环首尾两个节点也相邻额外加上首尾乘积if is_cycle:score dq[0] * dq[-1]return score---关键说明要点 说明连通分量分类 所有节点度数均为 2 → 环否则为链含孤立点处理顺序 环优先于链因为环的每个节点都有两条边大数在环中能产生更多乘积链按长度降序长链优先拿大数_calc_score 双端队列模拟最优排列。例如 [7..11] 填入 5 个节点的链排列为 8-10-11-9-7边权和 801109963 352环额外处理 环首尾相连所以 dq[0] * dq[-1] 是最后一条边的贡献