func countPairs(n int, edges [][]int, queries []int) []int {
deg := make([]int, n+1)
type edge struct{ x, y int }
cntE := map[edge]int{}
for _, e := range edges {
x, y := e[0], e[1]
if x > y {
x, y = y, x
}
deg[x]++
deg[y]++
cntE[edge{x, y}]++
}
// 统计 deg 中元素的出现次数
cntDeg := map[int]int{}
maxDeg := 0
for _, d := range deg[1:] {
cntDeg[d]++
maxDeg = max(maxDeg, d)
}
// 2)
k := maxDeg*2 + 2
cnts := make([]int, k)
for deg1, c1 := range cntDeg {
for deg2, c2 := range cntDeg {
if deg1 < deg2 {
cnts[deg1+deg2] += c1 * c2
} else if deg1 == deg2 {
cnts[deg1+deg2] += c1 * (c1 - 1) / 2
}
}
}
// 3)
for e, c := range cntE {
s := deg[e.x] + deg[e.y]
cnts[s]--
cnts[s-c]++
}
// 4) 计算 cnts 的后缀和
for i := k - 1; i > 0; i-- {
cnts[i-1] += cnts[i]
}
for i, q := range queries {
queries[i] = cnts[min(q+1, k-1)]
}
return queries
}
func min(a, b int) int { if b < a { return b }; return a }
func max(a, b int) int { if b > a { return b }; return a }
func countPairs(n int, edges [][]int, queries []int) []int {
// deg[i] 表示与点 i 相连的边的数目
deg := make([]int, n+1) // 节点编号从 1 到 n
type edge struct{ x, y int }
cntE := map[edge]int{}
for _, e := range edges {
x, y := e[0], e[1]
if x > y {
x, y = y, x
}
deg[x]++
deg[y]++
// 统计每条边的出现次数，注意 1-2 和 2-1 算同一条边
cntE[edge{x, y}]++
}
ans := make([]int, len(queries))
sortedDeg := append([]int(nil), deg...)
sort.Ints(sortedDeg) // 排序，为了双指针
for j, q := range queries {
left, right := 1, n // 相向双指针
for left < right {
if sortedDeg[left]+sortedDeg[right] <= q {
left++
} else {
ans[j] += right - left
right--
}
}
for e, c := range cntE {
s := deg[e.x] + deg[e.y]
if s > q && s-c <= q {
ans[j]--
}
}
}
return ans
}
class Solution {
public int[] countPairs(int n, int[][] edges, int[] queries) {
// deg[i] 表示与点 i 相连的边的数目
var deg = new int[n + 1]; // 节点编号从 1 到 n
var cntE = new HashMap<Integer, Integer>();
for (var e : edges) {
int x = e[0], y = e[1];
if (x > y) {
// 交换 x 和 y，因为 1-2 和 2-1 算同一条边
int tmp = x;
x = y;
y = tmp;
}
deg[x]++;
deg[y]++;
// 统计每条边的出现次数
// 用一个 int 存储两个不超过 65535 的数
cntE.merge(x << 16 | y, 1, Integer::sum); // cntE[x<<16|y]++
}
var ans = new int[queries.length];
var sortedDeg = deg.clone();
Arrays.sort(sortedDeg); // 排序，为了双指针
for (int j = 0; j < queries.length; j++) {
int q = queries[j];
int left = 1, right = n; // 相向双指针
while (left < right) {
if (sortedDeg[left] + sortedDeg[right] <= q) {
left++;
} else {
ans[j] += right - left;
right--;
}
}
for (var e : cntE.entrySet()) {
int k = e.getKey(), c = e.getValue();
int s = deg[k >> 16] + deg[k & 0xffff]; // 取出 k 的高 16 位和低 16 位
if (s > q && s - c <= q) {
ans[j]--;
}
}
}
return ans;
}
}
'''
点对的degree相加大于cnt, 把degree排序后，用相向双指针。
'''
class Solution:
def countPairs(self, n: int, edges: List[List[int]], queries: List[int]) -> List[int]:
# deg[i] 表示与点 i 相连的边的数目
deg = [0] * (n + 1) # 节点编号从 1 到 n
for x, y in edges:
deg[x] += 1
deg[y] += 1
# 统计每条边的出现次数，注意 1-2 和 2-1 算同一条边
cnt_e = Counter(tuple(sorted(e)) for e in edges)
ans = [0] * len(queries)
sorted_deg = sorted(deg) # 排序，为了双指针
for j, q in enumerate(queries):
left, right = 1, n # 相向双指针
while left < right:
if sorted_deg[left] + sorted_deg[right] <= q:
left += 1
else:
ans[j] += right - left
right -= 1
# 去重
for (x, y), c in cnt_e.items():
if q < deg[x] + deg[y] <= q + c:
ans[j] -= 1
return ans
