Tap here to switch tabs
Problem
Submissions

Problem: Count Pairs Of Nodes

Count Pairs Of Nodes asks you to process an undirected graph and answer queries by counting node pairs whose combined incident edges exceed each threshold, counting shared edges once.

Statement

You are given an undirected graph with n nodes labeled from 11 to n, and an array edges where each edges[i] = [u_i, v_i] represents an undirected edge between node u_i and node v_i. The graph may contain multiple edges connecting the same pair of nodes.

You are also given an integer array queries. The answer for query queries[j] is the total number of pairs of nodes (a,b)(a, b) satisfying 1≤a<b≤1 \leq a < b \leq n such that the number of edges incident to node aa or node bb is strictly greater than queries[j].

An edge is incident to node aa or node bb if at least one of its endpoints is node aa or node bb.

Return an array answers where answers[j] is the answer for queries[j].

Note: An edge directly connecting node aa and node bb is counted only once when determining the total number of incident edges for the pair (a,b)(a, b).

Constraints:

  • 2≤2 \leq n ≤2×104\leq 2 \times 10^4

  • 1≤1 \leq edges.length ≤105\leq 10^5

  • 1≤1 \leq u_i, v_i ≤\leq n

  • u_i ≠\neq v_i

  • 1≤1 \leq queries.length ≤20\leq 20

  • 0≤0 \leq queries[j] << edges.length

⋮
Tap here to switch tabs
Problem
Submissions

Problem: Count Pairs Of Nodes

Count Pairs Of Nodes asks you to process an undirected graph and answer queries by counting node pairs whose combined incident edges exceed each threshold, counting shared edges once.

Statement

You are given an undirected graph with n nodes labeled from 11 to n, and an array edges where each edges[i] = [u_i, v_i] represents an undirected edge between node u_i and node v_i. The graph may contain multiple edges connecting the same pair of nodes.

You are also given an integer array queries. The answer for query queries[j] is the total number of pairs of nodes (a,b)(a, b) satisfying 1≤a<b≤1 \leq a < b \leq n such that the number of edges incident to node aa or node bb is strictly greater than queries[j].

An edge is incident to node aa or node bb if at least one of its endpoints is node aa or node bb.

Return an array answers where answers[j] is the answer for queries[j].

Note: An edge directly connecting node aa and node bb is counted only once when determining the total number of incident edges for the pair (a,b)(a, b).

Constraints:

  • 2≤2 \leq n ≤2×104\leq 2 \times 10^4

  • 1≤1 \leq edges.length ≤105\leq 10^5

  • 1≤1 \leq u_i, v_i ≤\leq n

  • u_i ≠\neq v_i

  • 1≤1 \leq queries.length ≤20\leq 20

  • 0≤0 \leq queries[j] << edges.length