Solution

Method 1 – Degree Counting and Two Pointers

Intuition

The key is to count the number of pairs (a, b) such that the sum of their degrees (number of incident edges) minus the number of shared edges is greater than the query. We use sorting and two pointers to efficiently count such pairs for each query.

Approach

Count the degree of each node (number of edges connected to it).
For each edge, count the number of times each pair appears (to handle multiple edges between the same pair).
Sort the degree array.
For each query:
1. Use two pointers to count pairs (a, b) with degree[a] + degree[b] > query.

Related Tags