本题其它解法
本文涉及的基础知识点
题目
给你一个无向图，无向图由整数 n ，表示图中节点的数目，和 edges 组成，其中 edges[i] = [ui, vi] 表示 ui 和 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]
解释：每个点对中，与至少一个点相连的边的数目如上图所示。
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 * 104
1 <= edges.length <= 105
1 <= ui, vi <= n
ui != vi
1 <= queries.length <= 20
0 <= queries[j] < edges.length
分析
时间复杂度
每个查询的时间复杂度是O(nlogn+m)。m的边数。
步骤
每个查询分两步：
一，和a或b相连的边数，严格大于iQue的点对数量。注意，同时和a和b相连算两次，只和a或b相连算一次。
二，枚举各边。如果符合第一步，扣除本边数量后，不再符合题意则减掉。本解法在预处理阶段确保v[0]大于v[1]。
注意:本解题将a和b都减一，这样其范围为：[0,n)。
变量解释
| m_vNodeToCount | m_vNodeToCount[i]=x，有x条边和i相连 |
| m_vCounts | m_vNodeToCount的升序,第一步只考虑和a或b相连的边数，不需要知道a和b的具体值 |
| m_mMaskCount | 各边数量，key是a和b的编码，value是数量 |
代码
核心代码
class Solution { public: vector<int> countPairs(int n, vector<vector<int>>& edges, vector<int>& queries) { m_iN = n; m_vNodeToCount.resize(n); for (auto& v : edges) { if (v[0] < v[1]) { swap(v[0], v[1]); } v[0]--; v[1]--; m_vNodeToCount[v[0]]++; m_vNodeToCount[v[1]]++; m_mMaskCount[Mask(v[0], v[1])]++; } m_vCounts = m_vNodeToCount; sort(m_vCounts.begin(), m_vCounts.end()); vector<int> vRet; for (const auto& que : queries) { vRet.emplace_back(Query(que)); } return vRet; } int Query(int iQue)const { int iNum = 0;// 包括a或b的边数大于iQue的数量，(a,b)和(b,a)会重复结算 for (auto left = m_iN - 1; left >= 0 ; left--) { iNum += m_vCounts.end() - std::upper_bound(m_vCounts.begin()+left+1, m_vCounts.end(),iQue-m_vCounts[left]); } //扣处重复数量 for (const auto& [iMask, iNum1] : m_mMaskCount) { auto [a, b] = Parse(iMask); const int tmp = m_vNodeToCount[a] + m_vNodeToCount[b] - iQue; if (tmp > 0 ) { if (tmp <= iNum1) { iNum--; } } } return iNum; } int Mask(int a, int b) { return a * m_iUnit + b; } std::pair<int,int> Parse(const int iMask)const { return std::make_pair(iMask / m_iUnit, iMask % m_iUnit); } const int m_iUnit = 1000 * 100; unordered_map<int, int> m_mMaskCount; vector<int> m_vNodeToCount; vector<int> m_vCounts; int m_iN; };
测试用例
template <class T> void Assert(const T& t1, const T& t2) { assert(t1 == t2); } template <class T> void Assert(const vector<T>& v1, const vector<T>& v2) { if (v1.size() != v2.size()) { assert(false); return; } for (int i = 0; i < v1.size(); i++) { Assert(v1[i], v2[i]); } } int main() { int n; vector<vector<int>> edges; vector<int> queries; vector<int> res; { n = 4; edges = { {1,2},{2,4},{1,3},{2,3},{2,1} }; queries = { 2,3 }; Solution slu; res = slu.countPairs(n, edges, queries); Assert(res, vector<int>{6, 5}); } { 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 }; Solution slu; res = slu.countPairs(n, edges, queries); Assert(res, vector<int>{10, 10, 9, 8, 6}); } //CConsole::Out(res); }
2023年3月版代码
class Solution { public: vector countPairs(int n, vector<vector>& edges, vector& queries) { m_vDeg.resize(n + 1); m_iN = n; for (const auto& v : edges) { m_vDeg[v[0]]++; m_vDeg[v[1]]++; m_mEdgeNums[min(v[0], v[1])m_llMul + max(v[0], v[1])]++; } vector vRet; for (const auto& q : queries) { vRet.push_back(Query1(q) - Query2(q)); } return vRet; } long long Query1(int iQuery) { CTreeArr tree(1000100 + 1); long long iRet = 0; for (int i = 1; i <= m_iN; i++) { const int iMin = iQuery - m_vDeg[i]; const int iLessEqualNum = (iMin>=0) ? tree.Sum(iMin ) : 0; iRet += (i - 1) - iLessEqualNum; tree.Add(m_vDeg[i],1); } return iRet; } long long Query2(int iQuery) { long long llSub = 0; for (auto it : m_mEdgeNums) { const int iNum1 = m_vDeg[it.first%m_llMul] + m_vDeg[it.first/m_llMul]; if (iNum1 <= iQuery) { continue; } if (iNum1 - it.second <= iQuery) { llSub++; } } return llSub; } long long m_llMul = 1000 * 100; vector m_vDeg; std::unordered_map<long long, int> m_mEdgeNums; int m_iN; };
2023年7月版代码
class Solution { public: vector countPairs(int n, vector<vector>& edges, vector& queries) { m_vDeg.resize(n + 1); m_iN = n; for (const auto& v : edges) { m_vDeg[v[0]]++; m_vDeg[v[1]]++; m_mEdgeNums[min(v[0], v[1])m_llMul + max(v[0], v[1])]++; } vector vRet; for (const auto& q : queries) { vRet.push_back(Query1(q) - Query2(q)); } return vRet; } long long Query1(int iQuery) { CTreeArr tree(1000100 + 1); long long iRet = 0; for (int i = 1; i <= m_iN; i++) { const int iMin = iQuery - m_vDeg[i]; const int iLessEqualNum = (iMin>=0) ? tree.Sum(iMin ) : 0; iRet += (i - 1) - iLessEqualNum; tree.Add(m_vDeg[i],1); } return iRet; } long long Query2(int iQuery) { long long llSub = 0; for (auto it : m_mEdgeNums) { const int iNum1 = m_vDeg[it.first%m_llMul] + m_vDeg[it.first/m_llMul]; if (iNum1 <= iQuery) { continue; } if (iNum1 - it.second <= iQuery) { llSub++; } } return llSub; } long long m_llMul = 1000 * 100; vector m_vDeg; std::unordered_map<long long, int> m_mEdgeNums; int m_iN; };
