Skip to content
BASA DSA

Number of Connected Components In An Undirected Graph

MediumGraphs

Return the number of connected components in an undirected graph with n nodes labeled 0..n-1, including isolated nodes.

Example 1

Undirected input edges; isolated vertices are included.Undirected input edges; isolated vertices are included. Vertices: node 0: 0, node 1: 1, node 2: 2, node 3: 3, node 4: 4. Edges: node 0 (0) — node 1 (1); node 1 (1) — node 2 (2); node 3 (3) — node 4 (4).01234
Undirected input edges; isolated vertices are included.

Input
n = 5
edges = [[0,1],[1,2],[3,4]]
Output
2

Explanation

0,1,2 form one component and 3,4 another.

Example 2

Undirected input edges; isolated vertices are included.Undirected input edges; isolated vertices are included. Vertices: node 0: 0, node 1: 1, node 2: 2, node 3: 3. Edges: none.0123
Undirected input edges; isolated vertices are included.

Input
n = 4
edges = []
Output
4

Explanation

With no edges all four nodes are isolated components.

Example 3

Undirected input edges; isolated vertices are included.Undirected input edges; isolated vertices are included. Vertices: node 0: 0, node 1: 1, node 2: 2. Edges: node 0 (0) — node 1 (1); node 1 (1) — node 2 (2); node 0 (0) — node 2 (2).012
Undirected input edges; isolated vertices are included.

Input
n = 3
edges = [[0,1],[1,2],[0,2]]
Output
1

Explanation

All three nodes are connected despite their cycle, giving one component.

Constraints

  • 1 <= n <= 2000
  • Edges are distinct valid unordered pairs without self-loops

Function contractcountComponentsArguments: json, json
Loading draft…
SolutionRuns on your device