Leetcode P1782 统计点对的数目

Leetcode P1782 统计点对的数目

给你一个无向图，无向图由整数 n ，表示图中节点的数目，和 edges 组成，其中 $edges[i] = [u_i, v_i] $表示 u i u_i ui 和 v i v_i vi 之间有一条无向边。同时给你一个代表查询的整数数组 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]

示例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^4 1 <= edges.length <= 10^5 1 <= ui, vi <= n ui != vi 1 <= queries.length <= 20 0 <= queries[j] < edges.length

这是47场双周赛的最后一题，我没有参加，但估计这道题我也不会做。给一个图，统计点对(u,v)的数量，其中(u,v)满足和u或v连边的数量大于cnt。

首先容易想到，和u或v连接的边的数量是： d e g r e e [ u ] + d e g r e e [ v ] − m p [ u ] [ v ] degree[u]+degree[v]-mp[u][v] degree[u]+degree[v]−mp[u][v] 其中degree容易处理得到，代表一个点的度数。mp[u][v]是u和v之间边的数量，本来可以是个二维数组，但这里由于n的范围较大，可以用20001 * u + v代替点对(u,v)。所以，我们要找到满足 d e g r e e [ u ] + d e g r e e [ v ] − m p [ u ] [ v ] > c n t degree[u]+degree[v]-mp[u][v]>cnt degree[u]+degree[v]−mp[u][v]>cnt的点对(u,v)的数量。

暴力穷举显然会被卡。一个巧妙的思路是，先处理得到 d e g r e e [ u ] + d e g r e e [ v ] > c n t degree[u]+degree[v]>cnt degree[u]+degree[v]>cnt的点对数sum1，这个可以用双指针得到。再计算 d e g r e e [ u ] + d e g r e e [ v ] > c n t degree[u]+degree[v]>cnt degree[u]+degree[v]>cnt但 d e g r e e [ u ] + d e g r e e [ v ] − m p [ u ] [ v ] ≤ c n t degree[u]+degree[v]-mp[u][v]leq cnt degree[u]+degree[v]−mp[u][v]≤cnt的点对数量sum2，这样的点对一定在edge数组里，只需要遍历一遍edge就能得到…sum1-sum2即为答案。可以发现，很多数据规模直觉上无法解决的问题，可以分为两部分解决，用双指针巧妙优化。代码如下：

class Solution {
          
   
public:
    vector<int> countPairs(int n, vector<vector<int>>& edges, vector<int>& queries) {
          
   
        vector<int> res(queries.size());
        unordered_map<int, int> mp;
        int d[20010], degrees[20010];
        memset(d, 0, sizeof(d));
        for (auto &edge: edges) {
          
   
            int u = min(edge[0], edge[1]);
            int v = max(edge[0], edge[1]);
            mp[u * 20001 + v]++;
            d[u]++, d[v]++;
        }
        for (int i = 1; i <= n; i++) degrees[i] = i;
        sort(degrees + 1, degrees + n + 1, [&](int a, int b) {
          
   
            return d[a] < d[b];
        });
        for (int i = 0; i < queries.size(); i++) {
          
   
            int cnt = queries[i];
            int r = n, sum1 = 0;
            unordered_set<int> dup;
            for (int l = 1; l < n; l++) {
          
   
                while (r > l && d[degrees[l]] + d[degrees[r]] > cnt) r--;
                sum1 += r > l ? n - r : n - l;
            }
            for (auto &edge: edges) {
          
   
                int u = min(edge[0], edge[1]);
                int v = max(edge[0], edge[1]);
                if (d[u] + d[v] > cnt && d[u] + d[v] - mp[20001 * u + v] <= cnt) dup.insert(20001 * u + v);
            }
            res[i] = sum1 - dup.size();
        }
        return res;
    }
};