Tap here to switch tabs
Problem
Submissions

Problem: Count Unreachable Pairs of Nodes in an Undirected Graph

Count Unreachable Pairs of Nodes in an Undirected Graph gives you nodes and edges, then asks for the number of distinct node pairs with no path connecting them.

Statement

You are given an integer n representing the number of nodes in an undirected graph, with nodes labeled from 00 to n −1- 1. You are also given a 22D integer array edges, where edges[i] =[= [ a_i, b_i ]] indicates that an undirected edge exists between node a_i and node b_i.

Return the total number of pairs of distinct nodes such that there is no path between them.

Constraints:

  • 1≤1 \leq n ≤105\leq 10^5

  • 0≤0 \leq edges.length ≤2imes105\leq 2 imes 10^5

  • edges[i].length =2= 2

  • 0≤0 \leq a_i, b_i << n

  • a_i ≠\neq b_i

  • There are no repeated edges.

⋮
Tap here to switch tabs
Problem
Submissions

Problem: Count Unreachable Pairs of Nodes in an Undirected Graph

Count Unreachable Pairs of Nodes in an Undirected Graph gives you nodes and edges, then asks for the number of distinct node pairs with no path connecting them.

Statement

You are given an integer n representing the number of nodes in an undirected graph, with nodes labeled from 00 to n −1- 1. You are also given a 22D integer array edges, where edges[i] =[= [ a_i, b_i ]] indicates that an undirected edge exists between node a_i and node b_i.

Return the total number of pairs of distinct nodes such that there is no path between them.

Constraints:

  • 1≤1 \leq n ≤105\leq 10^5

  • 0≤0 \leq edges.length ≤2imes105\leq 2 imes 10^5

  • edges[i].length =2= 2

  • 0≤0 \leq a_i, b_i << n

  • a_i ≠\neq b_i

  • There are no repeated edges.