Formatted question description: https://leetcode.ca/all/1782.html

# 1782. Count Pairs Of Nodes

## Level

Hard

## Description

You are given an undirected graph represented by an integer `n`

, which is the number of nodes, and `edges`

, where `edges[i] = [u_i, v_i]`

which indicates that there is an undirected edge between `u_i`

and `v_i`

. You are also given an integer array `queries`

.

The answer to the `j-th`

query is the number of pairs of nodes `(a, b)`

that satisfy the following conditions:

`a < b`

`cnt`

is**strictly greater**than`queries[j]`

, where`cnt`

is the number of edges incident to`a`

**or**`b`

.

Return an array `answers`

such that `answers.length == queries.length`

and `answers[j]`

is the answer of the `j-th`

query.

Note that there can be **repeated edges**.

**Example 1:**

**Input:** n = 4, edges = [[1,2],[2,4],[1,3],[2,3],[2,1]], queries = [2,3]

**Output:** [6,5]

**Explanation:** The number of edges incident to at least one of each pair is shown above.

**Example 2:**

**Input:** 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]

**Output:** [10,10,9,8,6]

**Constraints:**

`2 <= n <= 2 * 10^4`

`1 <= edges.length <= 10^5`

`1 <= u_i, v_i <= n`

`u_i != v_i`

`1 <= queries.length <= 20`

`0 <= queries[j] < edges.length`

## Solution

First, calculate the degrees of each node and the counts of each edge. Next, use another array `arr`

to store the degrees and sort `arr`

. Then, for each query, use two pointers to calculate the number of pairs of nodes that satisfy the conditions. Finally, return the query result.

```
class Solution {
public int[] countPairs(int n, int[][] edges, int[] queries) {
final int FACTOR = 100000;
int[] degrees = new int[n + 1];
int[] arr = new int[n + 1];
int length = queries.length;
int[] pairs = new int[length];
Map<Integer, Integer> map = new HashMap<Integer, Integer>();
for (int[] edge : edges) {
int u = Math.min(edge[0], edge[1]);
int v = Math.max(edge[0], edge[1]);
degrees[u]++;
degrees[v]++;
int key = u * FACTOR + v;
map.put(key, map.getOrDefault(key, 0) + 1);
}
for (int i = 1; i <= n; i++)
arr[i] = degrees[i];
Arrays.sort(arr);
for (int i = 0; i < length; i++) {
int low = 1, high = n;
while (low < high) {
while (low < high && arr[low] + arr[high] <= queries[i])
low++;
if (low < high)
pairs[i] += high - low;
high--;
}
if (pairs[i] != 0) {
Set<Integer> visited = new HashSet<Integer>();
for (int[] edge : edges) {
int u = Math.min(edge[0], edge[1]);
int v = Math.max(edge[0], edge[1]);
int key = u * FACTOR + v;
if (visited.add(key)) {
int pair = degrees[u] + degrees[v] - map.get(key);
if (degrees[u] + degrees[v] > queries[i] && pair <= queries[i])
pairs[i]--;
}
}
}
}
return pairs;
}
}
```