Hard

题目描述

给定一个有 n 个节点的无向连通图，节点编号从 0 到 n - 1。每个节点最多连接 2 个其他节点。

图由 m 条边组成，用二维数组 edges 表示，其中 edges[i] = [ai, bi] 表示节点 ai 和 bi 之间有一条边。

你需要为每个节点分配一个从 1 到 n 的唯一值。边的值是连接的两个节点值的乘积。

你的得分是图中所有边值的总和。

返回你能获得的最大得分。

示例 1：

输入：n = 4, edges = [[0,1],[1,2],[2,3]]
输出：23
解释：
上图展示了节点值的最优分配。边值的总和为：(1 * 3) + (3 * 4) + (4 * 2) = 23。

示例 2：

输入：n = 6, edges = [[0,3],[4,5],[2,0],[1,3],[2,4],[1,5]]
输出：82
解释：
上图展示了节点值的最优分配。边值的总和为：(1 * 2) + (2 * 4) + (4 * 6) + (6 * 5) + (5 * 3) + (3 * 1) = 82。

约束条件：

  • 1 <= n <= 5 * 10^4
  • m == edges.length
  • 1 <= m <= n
  • edges[i].length == 2
  • 0 <= ai, bi < n
  • ai != bi
  • 没有重复的边
  • 图是连通的
  • 每个节点最多连接 2 个其他节点

提示：

  • 图要么是简单路径，要么是环
  • 贪心地为节点分配值

解题思路

这道题的关键观察是图的特殊性质：每个节点最多连接2个其他节点，这意味着图要么是一条路径，要么是一个环。

核心思路：

  1. 度数分析：由于每个节点最多有2条边，图的结构非常简单。我们需要根据每个节点的度数来分配权重。

  2. 贪心策略：要最大化边值的和，我们应该让度数高的节点分配更大的值。因为度数高的节点参与更多的乘积运算，对总和贡献更大。

  3. 排序分配：

    • 计算每个节点的度数
    • 按度数从大到小排序节点
    • 将最大的权重分配给度数最高的节点

  4. 特殊情况处理：

    • 如果图是路径：两个端点度数为1，中间节点度数为2
    • 如果图是环：所有节点度数都为2

算法步骤：

  1. 构建图并计算每个节点的度数
  2. 创建(节点, 度数)对的列表
  3. 按度数降序排序
  4. 依次分配权重n, n-1, …, 1
  5. 计算所有边的权重乘积之和

这种贪心策略是最优的，因为我们总是让参与更多乘积的节点获得更大的权重。

代码实现

class Solution {
public:
    long long maxScore(int n, vector<vector<int>>& edges) {
        vector<int> degree(n, 0);
        vector<vector<int>> graph(n);
        
        // 建图并计算度数
        for (auto& edge : edges) {
            int u = edge[0], v = edge[1];
            degree[u]++;
            degree[v]++;
            graph[u].push_back(v);
            graph[v].push_back(u);
        }
        
        // 按度数降序排序节点
        vector<pair<int, int>> nodeDegree;
        for (int i = 0; i < n; i++) {
            nodeDegree.push_back({degree[i], i});
        }
        sort(nodeDegree.rbegin(), nodeDegree.rend());
        
        // 分配权重
        vector<int> values(n);
        for (int i = 0; i < n; i++) {
            values[nodeDegree[i].second] = n - i;
        }
        
        // 计算总和
        long long result = 0;
        for (auto& edge : edges) {
            int u = edge[0], v = edge[1];
            result += (long long)values[u] * values[v];
        }
        
        return result;
    }
};

class Solution:
    def maxScore(self, n: int, edges: List[List[int]]) -> int:
        # 计算每个节点的度数
        degree = [0] * n
        for u, v in edges:
            degree[u] += 1
            degree[v] += 1
        
        # 按度数降序排序节点
        nodes_by_degree = sorted(range(n), key=lambda x: degree[x], reverse=True)
        
        # 分配权重：度数高的节点分配大权重
        values = [0] * n
        for i, node in enumerate(nodes_by_degree):
            values[node] = n - i
        
        # 计算所有边的权重乘积之和
        result = 0
        for u, v in edges:
            result += values[u] * values[v]
        
        return result

public class Solution {
    public long MaxScore(int n, int[][] edges) {
        int[] degree = new int[n];
        
        // 计算每个节点的度数
        foreach (var edge in edges) {
            degree[edge[0]]++;
            degree[edge[1]]++;
        }
        
        // 创建节点和度数的配对，按度数降序排序
        var nodeDegree = new List<(int deg, int node)>();
        for (int i = 0; i < n; i++) {
            nodeDegree.Add((degree[i], i));
        }
        nodeDegree.Sort((a, b) => b.deg.CompareTo(a.deg));
        
        // 分配权重
        int[] values = new int[n];
        for (int i = 0; i < n; i++) {
            values[nodeDegree[i].node] = n - i;
        }
        
        // 计算总和
        long result = 0;
        foreach (var edge in edges) {
            result += (long)values[edge[0]] * values[edge[1]];
        }
        
        return result;
    }
}

var maxScore = function(n, edges) {
    // 计算每个节点的度数
    const degree = new Array(n).fill(0);
    for (const [u, v] of edges) {
        degree[u]++;
        degree[v]++;
    }
    
    // 创建节点索引数组并按度数降序排序
    const nodes = Array.from({length: n}, (_, i) => i);
    nodes.sort((a, b) => degree[b] - degree[a]);
    
    // 分配权重：度数高的节点分配大权重
    const values = new Array(n);
    for (let i = 0; i < n; i++) {
        values[nodes[i]] = n - i;
    }
    
    // 计算所有边的权重乘积之和
    let result = 0;
    for (const [u, v] of edges) {
        result += values[u] * values[v];
    }
    
    return result;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度大小
时间复杂度O(n log n)
空间复杂度O(n)

解释：

  • 时间复杂度：计算度数需要 O(m) 时间，排序需要 O(n log n) 时间，计算结果需要 O(m) 时间。由于 m ≤ n，总时间复杂度为 O(n log n)
  • 空间复杂度：需要存储度数数组、节点排序数组和权重数组，空间复杂度为 O(n)