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

以下是 LeetCode 3547. 图中边值的最大和 的 C 实现。解题思路由于每个节点最多与其他两个节点相连整个图由若干链和环组成。1. 连通分量分类用 DFS 找出所有连通分量。若分量内所有节点度数均为 2则为环否则为链孤立点不贡献边权忽略。2. 处理顺序先处理环每个节点有两条边大数在环中能产生更多乘积再处理链按长度降序长链优先拿大数。3. 填数策略将剩余的最大数放在连通分量中间次大数交替向两边扩展使得大数尽量相邻双端队列模拟。时间复杂度 O(n \log n)空间复杂度 O(n)。---C 代码cpp#include vector#include deque#include algorithmusing namespace std;class Solution {public:long long maxScore(int n, vectorvectorint edges) {vectorvectorint graph(n);for (auto edge : edges) {int u edge[0], v edge[1];graph[u].push_back(v);graph[v].push_back(u);}vectorbool seen(n, false);vectorint cycleSizes; // 环的大小vectorint pathSizes; // 链的大小// 遍历每个连通分量for (int i 0; i n; i) {if (seen[i]) continue;// DFS 收集连通分量vectorint component;vectorint stack {i};seen[i] true;while (!stack.empty()) {int u stack.back();stack.pop_back();component.push_back(u);for (int v : graph[u]) {if (!seen[v]) {seen[v] true;stack.push_back(v);}}}// 判断是否为环所有节点度数均为 2bool isCycle true;for (int u : component) {if (graph[u].size() ! 2) {isCycle false;break;}}if (isCycle) {cycleSizes.push_back(component.size());} else if (component.size() 1) {pathSizes.push_back(component.size());}// 孤立点size 1不贡献边权无需处理}long long ans 0;long long remaining n;// 先处理环从剩余的最大数中分配for (int size : cycleSizes) {ans calcScore(remaining - size 1, remaining, true);remaining - size;}// 链按长度从大到小排序优先处理长链sort(pathSizes.rbegin(), pathSizes.rend());for (int size : pathSizes) {ans calcScore(remaining - size 1, remaining, false);remaining - size;}return ans;}private:/*** 将 [left, right] 范围内的数填入一个连通分量计算最大边权和。** 策略双端队列模拟中间放大数向两边递减的排列。* 初始放入两个 right从 right-1 递减到 left每次取出队首与当前值相乘* 再将当前值放入队尾。*/long long calcScore(long long left, long long right, bool isCycle) {dequelong long dq;dq.push_back(right);dq.push_back(right);long long score 0;for (long long val right - 1; val left; --val) {long long windowVal dq.front();dq.pop_front();score windowVal * val;dq.push_back(val);}// 如果是环首尾两个节点也相邻额外加上首尾乘积if (isCycle) {score dq.front() * dq.back();}return score;}};---关键说明要点 说明连通分量分类 所有节点度数均为 2 → 环否则为链含孤立点处理顺序 环优先于链因为环的每个节点都有两条边大数在环中能产生更多乘积链按长度降序长链优先拿大数calcScore 双端队列模拟最优排列。例如 [7..11] 填入 5 个节点的链排列为 8-10-11-9-7边权和最大环额外处理 环首尾相连所以 dq.front() * dq.back() 是最后一条边的贡献