统计点对的数目

难度: Hard

给你一个无向图，无向图由整数 n ，表示图中节点的数目，和 edges 组成，其中 edges[i] = [u_i, v_i] 表示 u_i 和 v_i之间有一条无向边。同时给你一个代表查询的整数数组 queries 。

第 j 个查询的答案是满足如下条件的点对 (a, b) 的数目：

a < b
cnt 是与 a 或者 b 相连的边的数目，且 cnt 严格大于 queries[j] 。

请你返回一个数组 answers ，其中 answers.length == queries.length 且 answers[j] 是第 j 个查询的答案。

请注意，图中可能会有 多重边 。

示例 1：

输入：n = 4, edges = [[1,2],[2,4],[1,3],[2,3],[2,1]], queries = [2,3]
输出：[6,5]
解释：每个点对中，与至少一个点相连的边的数目如上图所示。
answers[0] = 6。所有的点对(a, b)中边数和都大于2，故有6个；
answers[1] = 5。所有的点对(a, b)中除了(3,4)边数等于3，其它点对边数和都大于3，故有5个。

示例 2：

输入：n = 5, edges = [[1,5],[1,5],[3,4],[2,5],[1,3],[5,1],[2,3],[2,5]], queries = [1,2,3,4,5]
输出：[10,10,9,8,6]

提示：

2 <= n <= 2 * 10⁴
1 <= edges.length <= 10⁵
1 <= u_i, v_i <= n
u_i!= v_i
1 <= queries.length <= 20
0 <= queries[j] < edges.length

Submission

运行时间: 279 ms

内存: 50.3 MB

class Solution:
    def countPairs(self, n: int, edges: List[List[int]], queries: List[int]) -> List[int]:
        
        deg = [0] * (n + 1)
        cnt_e = dict()  # 比 Counter 快一点
        for x, y in edges:
            if x > y: x, y = y, x
            deg[x] += 1
            deg[y] += 1
            cnt_e[(x, y)] = cnt_e.get((x, y), 0) + 1
        cnt_deg = Counter(deg[1:])

        # 2)
        cnts = [0] * (max(deg) * 2 + 2)
        for deg1, c1 in cnt_deg.items():
            for deg2, c2 in cnt_deg.items():
                if deg1 < deg2:
                    cnts[deg1 + deg2] += c1 * c2
                elif deg1 == deg2:
                    cnts[deg1 + deg2] += c1 * (c1 - 1) // 2

        # 3)
        for (x, y), c in cnt_e.items():
            s = deg[x] + deg[y]
            cnts[s] -= 1
            cnts[s - c] += 1

        # 4) 计算 cnts 的后缀和
        for i in range(len(cnts) - 1, 0, -1):
            cnts[i - 1] += cnts[i]

        for i, q in enumerate(queries):
            queries[i] = cnts[min(q + 1, len(cnts) - 1)]
        return queries

Explain

此题解采用了一种基于计数的方法，通过统计每个节点的度数，以及每种度数出现的频率，来高效计算满足条件的点对数量。主要步骤如下： 1. 计算每个节点的度数，并统计每条边出现的次数。 2. 使用度数统计来预计算所有可能的度数和的点对数量，这里忽略了多重边的特殊处理。 3. 调整计数以考虑多重边，即对于图中实际存在的每条边，调整其对应的度数和的点对计数。 4. 通过计算后缀和来快速回答每个查询，即对于每个查询值，计算所有度数和大于该查询值的点对数量。

时间复杂度: O(E + d^2 + Q)

空间复杂度: O(n + E + d + Q)

class Solution:
    def countPairs(self, n: int, edges: List[List[int]], queries: List[int]) -> List[int]:
        
        deg = [0] * (n + 1)  # 存储每个节点的度数
        cnt_e = dict()  # 存储每条边出现的次数
        for x, y in edges:
            if x > y: x, y = y, x
            deg[x] += 1
            deg[y] += 1
            cnt_e[(x, y)] = cnt_e.get((x, y), 0) + 1
        cnt_deg = Counter(deg[1:])  # 统计每个度数出现的频率

        cnts = [0] * (max(deg) * 2 + 2)
        for deg1, c1 in cnt_deg.items():
            for deg2, c2 in cnt_deg.items():
                if deg1 < deg2:
                    cnts[deg1 + deg2] += c1 * c2
                elif deg1 == deg2:
                    cnts[deg1 + deg2] += c1 * (c1 - 1) // 2

        for (x, y), c in cnt_e.items():
            s = deg[x] + deg[y]
            cnts[s] -= 1
            cnts[s - c] += 1

        for i in range(len(cnts) - 1, 0, -1):
            cnts[i - 1] += cnts[i]

        for i, q in enumerate(queries):
            queries[i] = cnts[min(q + 1, len(cnts) - 1)]
        return queries

Explore

在计算点对的过程中，题解首先计算了所有可能的度数和，然后针对每条边进行调整。具体地，对于图中的每条边(x, y)，若边(x, y)为多重边，其存在次数为c，则会影响节点x和y的度数和的计算。首先，原始计算中假设x和y之间的联系只计算一次，因此需要从度数和s（deg[x] + deg[y]）中减去这个点对一次，然后再加入调整后的点对计数，即在s - c（实际的度数和，考虑到多重边应该减去重复计算的边数）处加一。这种调整是必须的，因为多重边意味着在计算x和y的度数和时，可能会重复计数，导致对该点对的统计不准确。

使用`c1 * (c1 - 1) // 2`的计算方式是为了统计相同度数的节点间的点对数量。这个计算公式基于组合数学中的组合公式，即从c1个相同度数的节点中选取2个节点可以形成的点对数。公式中的`c1 * (c1 - 1) / 2`表示从c1个元素中任意选择2个不同的元素的方法数，这是因为每个点与其他点都可以形成一个不重复的点对，而每个点对在统计时只能计算一次，故需要除以2以避免重复计数。

后缀和数组是通过从后往前累加得到的。具体来说，首先计算了不同度数和下的点对数，然后从数组的最后一个元素开始向前累加，每个位置存储的是从当前度数和到最大度数和之间所有点对的总和。这样构建的后缀和数组使得对于任何一个查询值q，只需通过访问数组中的q+1位置即可直接得到所有度数和大于q的点对总数，极大提高了查询效率，避免了对每个查询重复计算或线性扫描的需要。