1782. Count Pairs Of Nodes Hard

1/**
2 * [1782] Count Pairs Of Nodes
3 *
4 * 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.
5 * Let incident(a, b) be defined as the number of edges that are connected to either node a or b.
6 * The answer to the j^th query is the number of pairs of nodes (a, b) that satisfy both of the following conditions:
7 * 
8 * 	a < b
9 * 	incident(a, b) > queries[j]
10 * 
11 * Return an array answers such that answers.length == queries.length and answers[j] is the answer of the j^th query.
12 * Note that there can be multiple edges between the same two nodes.
13 *  
14 * Example 1:
15 * <img alt="" src="https://assets.leetcode.com/uploads/2021/06/08/winword_2021-06-08_00-58-39.png" style="width: 529px; height: 305px;" />
16 * Input: n = 4, edges = [[1,2],[2,4],[1,3],[2,3],[2,1]], queries = [2,3]
17 * Output: [6,5]
18 * Explanation: The calculations for incident(a, b) are shown in the table above.
19 * The answers for each of the queries are as follows:
20 * - answers[0] = 6. All the pairs have an incident(a, b) value greater than 2.
21 * - answers[1] = 5. All the pairs except (3, 4) have an incident(a, b) value greater than 3.
22 * 
23 * Example 2:
24 * 
25 * 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]
26 * Output: [10,10,9,8,6]
27 * 
28 *  
29 * Constraints:
30 * 
31 * 	2 <= n <= 2 * 10^4
32 * 	1 <= edges.length <= 10^5
33 * 	1 <= ui, vi <= n
34 * 	ui != vi
35 * 	1 <= queries.length <= 20
36 * 	0 <= queries[j] < edges.length
37 * 
38 */
39pub struct Solution {}
40
41// problem: https://leetcode.com/problems/count-pairs-of-nodes/
42// discuss: https://leetcode.com/problems/count-pairs-of-nodes/discuss/?currentPage=1&orderBy=most_votes&query=
43
44// submission codes start here
45
46impl Solution {
47    pub fn count_pairs(n: i32, edges: Vec<Vec<i32>>, queries: Vec<i32>) -> Vec<i32> {
48        vec![]
49    }
50}
51
52// submission codes end
53
54#[cfg(test)]
55mod tests {
56    use super::*;
57
58    #[test]
59    fn test_1782() {
60    }
61}
62