/323. Number of Connected Components in an Undirected Graph

323. Number of Connected Components in an Undirected Graph

Medium

Graphs64.8% acceptance

Given an undirected graph with n nodes labeled from 0 to n-1 and a list of undirected edges, determine the number of connected components in the graph. Each edge is represented as a pair of nodes [u, v].

Example 1

Input: node_count=7, edge_list=[[0,1],[1,2],[3,4],[5,6]]

Output: 3

Explanation: There are three connected components: {0,1,2}, {3,4}, {5,6}.

Example 2

Input: node_count=5, edge_list=[[0,1],[1,2],[2,3],[3,4]]

Output: 1

Explanation: All nodes are connected in a single component.

Constraints

1 <= node_count <= 10000
0 <= len(edge_list) <= node_count * (node_count - 1) // 2
Each edge in edge_list is a list [u, v] with 0 <= u, v < node_count
No duplicate edges
No self-loops

Python (current runtime)

Case 1

Input: node_count=6, edge_list=[[0,1],[2,3],[4,5]]

Expected: 3

Case 2

Input: node_count=4, edge_list=[[0,1],[2,3]]

Expected: 2

Case 3

Input: node_count=3, edge_list=[]

Expected: 3

Case 4

Input: node_count=8, edge_list=[[0,1],[1,2],[3,4],[4,5],[6,7]]

Expected: 3