Count Pairs Of Nodes
You are given an undirected graph defined by an integer n, the number of nodes, and a 2D integer array edges, the edges in the graph, where edges[i] = [ui, vi] indicates that there is an undirected edge between ui and vi. You are also given an integer array queries.
Let incident(a, b) be defined as the number of edges that are connected to either node a or b.
The answer to the j^th query is the number of pairs of nodes (a, b) that satisfy both of the following conditions:
a < bincident(a, b) > queries[j]
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 multiple edges between the same two nodes.
Example 1
Input
n = 4, edges = [[1,2],[2,4],[1,3],[2,3],[2,1]], queries = [2,3]Output
[6,5]All pairs have an
incident(a, b) value greater than 2, and all pairs except (3, 4) have an incident(a, b) value greater than 3.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]For the five queries, the counts of pairs with
incident(a, b) greater than each query value are 10, 10, 9, 8, and 6.Constraints
- 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