Asked at

Number of Connected Components

Medium
VerifiedDFSBFSUnion FindGraph~20 min

You’re given an undirected graph with n nodes 0..n-1 and edge list edges, where edges[i] = [u, v]. Count the connected components.

Return the count. The input arrives as a single object { n, edges }.

Examples

in{ n: 5, edges: [[0,1],[1,2],[3,4]] }
out2

Components {0,1,2} and {3,4}.

in{ n: 5, edges: [[0,1],[1,2],[2,3],[3,4]] }
out1

A single chain links every node.

Constraints

  • 1 ≤ n ≤ 2000
  • Edges are undirected: edges[i] = [u, v]
  • 0 ≤ u, v < n

Get help

🔑

Sign in to solve

Sign in to write, run, and submit your solution — and to pick up where your iOS flow left off.