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 < bincident(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:
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 <= nui != vi 1 <= queries.length <= 200 <= queries[j] < edges.lengthSolutions# 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
copy
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 ;
}
}
copy
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 ;
}
};
copy
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
}
copy
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 ;
}
copy
