Description#
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 jth
query is the number of pairs of nodes (a, b)
that satisfy both of the following conditions:
a < b
incident(a, b) > queries[j]
Return an array answers
such that answers.length == queries.length
and answers[j]
is the answer of the jth
query.
Note that there can be multiple edges between the same two nodes.
Example 1:
![](https://spcdn.pages.dev/leetcode/problems/1782.Count%20Pairs%20Of%20Nodes/images/winword_2021-06-08_00-58-39.png)
Input: n = 4, edges = [[1,2],[2,4],[1,3],[2,3],[2,1]], queries = [2,3]
Output: [6,5]
Explanation: The calculations for incident(a, b) are shown in the table above.
The answers for each of the queries are as follows:
- answers[0] = 6. All the pairs have an incident(a, b) value greater than 2.
- answers[1] = 5. All the 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]
Constraints:
2 <= n <= 2 * 104
1 <= edges.length <= 105
1 <= ui, vi <= n
ui != vi
1 <= queries.length <= 20
0 <= queries[j] < edges.length
Solutions#
Solution 1#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| class Solution:
def countPairs(
self, n: int, edges: List[List[int]], queries: List[int]
) -> List[int]:
cnt = [0] * n
g = defaultdict(int)
for a, b in edges:
a, b = a - 1, b - 1
a, b = min(a, b), max(a, b)
cnt[a] += 1
cnt[b] += 1
g[(a, b)] += 1
s = sorted(cnt)
ans = [0] * len(queries)
for i, t in enumerate(queries):
for j, x in enumerate(s):
k = bisect_right(s, t - x, lo=j + 1)
ans[i] += n - k
for (a, b), v in g.items():
if cnt[a] + cnt[b] > t and cnt[a] + cnt[b] - v <= t:
ans[i] -= 1
return ans
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
| class Solution {
public int[] countPairs(int n, int[][] edges, int[] queries) {
int[] cnt = new int[n];
Map<Integer, Integer> g = new HashMap<>();
for (var e : edges) {
int a = e[0] - 1, b = e[1] - 1;
++cnt[a];
++cnt[b];
int k = Math.min(a, b) * n + Math.max(a, b);
g.merge(k, 1, Integer::sum);
}
int[] s = cnt.clone();
Arrays.sort(s);
int[] ans = new int[queries.length];
for (int i = 0; i < queries.length; ++i) {
int t = queries[i];
for (int j = 0; j < n; ++j) {
int x = s[j];
int k = search(s, t - x, j + 1);
ans[i] += n - k;
}
for (var e : g.entrySet()) {
int a = e.getKey() / n, b = e.getKey() % n;
int v = e.getValue();
if (cnt[a] + cnt[b] > t && cnt[a] + cnt[b] - v <= t) {
--ans[i];
}
}
}
return ans;
}
private int search(int[] arr, int x, int i) {
int left = i, right = arr.length;
while (left < right) {
int mid = (left + right) >> 1;
if (arr[mid] > x) {
right = mid;
} else {
left = mid + 1;
}
}
return left;
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
| class Solution {
public:
vector<int> countPairs(int n, vector<vector<int>>& edges, vector<int>& queries) {
vector<int> cnt(n);
unordered_map<int, int> g;
for (auto& e : edges) {
int a = e[0] - 1, b = e[1] - 1;
++cnt[a];
++cnt[b];
int k = min(a, b) * n + max(a, b);
++g[k];
}
vector<int> s = cnt;
sort(s.begin(), s.end());
vector<int> ans(queries.size());
for (int i = 0; i < queries.size(); ++i) {
int t = queries[i];
for (int j = 0; j < n; ++j) {
int x = s[j];
int k = upper_bound(s.begin() + j + 1, s.end(), t - x) - s.begin();
ans[i] += n - k;
}
for (auto& [k, v] : g) {
int a = k / n, b = k % n;
if (cnt[a] + cnt[b] > t && cnt[a] + cnt[b] - v <= t) {
--ans[i];
}
}
}
return ans;
}
};
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
| func countPairs(n int, edges [][]int, queries []int) []int {
cnt := make([]int, n)
g := map[int]int{}
for _, e := range edges {
a, b := e[0]-1, e[1]-1
cnt[a]++
cnt[b]++
if a > b {
a, b = b, a
}
g[a*n+b]++
}
s := make([]int, n)
copy(s, cnt)
sort.Ints(s)
ans := make([]int, len(queries))
for i, t := range queries {
for j, x := range s {
k := sort.Search(n, func(h int) bool { return s[h] > t-x && h > j })
ans[i] += n - k
}
for k, v := range g {
a, b := k/n, k%n
if cnt[a]+cnt[b] > t && cnt[a]+cnt[b]-v <= t {
ans[i]--
}
}
}
return ans
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
| function countPairs(n: number, edges: number[][], queries: number[]): number[] {
const cnt: number[] = new Array(n).fill(0);
const g: Map<number, number> = new Map();
for (const [a, b] of edges) {
++cnt[a - 1];
++cnt[b - 1];
const k = Math.min(a - 1, b - 1) * n + Math.max(a - 1, b - 1);
g.set(k, (g.get(k) || 0) + 1);
}
const s = cnt.slice().sort((a, b) => a - b);
const search = (nums: number[], x: number, l: number): number => {
let r = nums.length;
while (l < r) {
const mid = (l + r) >> 1;
if (nums[mid] > x) {
r = mid;
} else {
l = mid + 1;
}
}
return l;
};
const ans: number[] = [];
for (const t of queries) {
let res = 0;
for (let j = 0; j < s.length; ++j) {
const k = search(s, t - s[j], j + 1);
res += n - k;
}
for (const [k, v] of g) {
const a = Math.floor(k / n);
const b = k % n;
if (cnt[a] + cnt[b] > t && cnt[a] + cnt[b] - v <= t) {
--res;
}
}
ans.push(res);
}
return ans;
}
|