Practice/Amazon/Leetcode 323. Number of Connected Components in an Undirected Graph

Leetcode 323. Number of Connected Components in an Undirected Graph

CodingOptional

Problem

You are given a network of n nodes labeled from 0 to n-1, along with a list of bidirectional connections between pairs of nodes. Your task is to determine how many separate clusters (connected components) exist in this network.

Two nodes belong to the same cluster if there is a path of connections between them, either directly or through other nodes. Nodes that cannot reach each other through any sequence of connections belong to different clusters.

Requirements

1. Count the total number of disconnected clusters in the network
2. Handle graphs where some nodes may have no connections
3. Treat all edges as bidirectional (undirected graph)
4. Each node can only belong to exactly one cluster

Constraints

• 1 <= n <= 2000 (number of nodes)
• 0 <= edges.length <= 5000 (number of connections)
• edges[i].length == 2 (each edge connects exactly two nodes)
• 0 <= edges[i][0], edges[i][1] < n (valid node indices)
• edges[i][0] != edges[i][1] (no self-loops)
• There are no duplicate edges
• Expected time complexity: O(n + e) where e is the number of edges
• Expected space complexity: O(n)

Examples

Example 1:

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

• Cluster 1: nodes {0, 1, 2} are connected
• Cluster 2: nodes {3, 4} are connected
• Node 3 is isolated and forms its own cluster Total: 2 clusters `

Example 2:

Input: n = 4, edges = [[0,1],[1,2],[2,3]] Output: 1 Explanation: All nodes are connected in a chain: 0 - 1 - 2 - 3

Example 3:

Input: n = 6, edges = [] Output: 6 Explanation: With no edges, each of the 6 nodes is its own isolated cluster