Number of Connected Components In An Undirected Graph

Medium · Graphs

You are given an integer n representing nodes labeled from 0 to n-1, and a list of edges where each edge connects two of those nodes. The graph has no direction on its edges. Count how many separate groups of nodes exist, where a group is a maximal set of nodes that can all reach each other by following edges (isolated nodes with no edges count as their own group).

Examples

Input:  n = 5, edges = [[0,1],[1,2],[3,4]]
Output: 2
Why:    Nodes 0,1,2 are linked into one group and nodes 3,4 form another group, giving 2 groups total.

Input:  n = 5, edges = [[0,1],[1,2],[2,3],[3,4]]
Output: 1
Why:    All nodes are chained together into a single connected group.

Input:  n = 4, edges = []
Output: 4
Why:    With no edges, every node is isolated and forms its own group.

Constraints

1 <= n <= 2000, 0 <= edges.length <= 5000, edges[i].length == 2, 0 <= edges[i][0], edges[i][1] < n, no duplicate edges and no self-loops

Practise it by voice

Describe the solution out loud and the interviewer writes exactly what you say, asks when you are vague, and runs the tests in your browser.

Practise Number of Connected Components In An Undirected Graph

This statement is written for CodeSpeek. The problem is part of the NeetCode 150 list; Watch NeetCode's explanation of Number of Connected Components In An Undirected Graph. Reference solutions from the NeetCode repository (MIT) are used to verify our tests.