> ## Documentation Index
> Fetch the complete documentation index at: https://leetcode-py.wisl.dev/llms.txt
> Use this file to discover all available pages before exploring further.

> ## Agent Instructions
> leetcode-py is a Python LeetCode practice environment generator with one CLI: lcpy. It is not a service or platform.
> Each problem is a directory under leetcode/ with README.md, solution.py, test_solution.py, helpers.py, and playground.ipynb. lcpy gen creates them from JSON templates bundled with the package.
> Examples are backed by tests; copy them verbatim.

# Number of Connected Components in an

> Tested Python solution for LeetCode 323 with 18 pytest cases. Generate a practice environment with lcpy.

LeetCode 323, Medium. Topics: Depth-First Search, Breadth-First Search, Union Find, Graph. [View on LeetCode](https://leetcode.com/problems/number-of-connected-components-in-an-undirected-graph/description/).

Generate this problem as a practice environment: tested reference solution, 18 [parametrized pytest cases](/practice/testing), and a playground notebook:

```bash theme={"theme":{"light":"github-light","dark":"github-dark"}}
lcpy gen -n 323   # by problem number
lcpy gen -s number_of_connected_components_in_an_undirected_graph   # by problem name
```

## Problem

Given `n` nodes labeled from `0` to `n - 1` and a list of undirected edges (each edge is a pair of nodes), write a function to find the number of connected components in an undirected graph.

### Examples

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

     0          3
     |          |
     1 --- 2    4

Output: 2
```

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

     0           4
     |           |
     1 --- 2 --- 3

Output: 1
```

### Constraints

* 1 \<= n \<= 2000
* 1 \<= edges.length \<= 5000
* edges\[i].length == 2
* 0 \<= ai, bi \< n
* ai != bi
* There are no repeated edges.

**Note:** You can assume that no duplicate edges will appear in edges. Since all edges are undirected, \[0, 1] is the same as \[1, 0] and thus will not appear together in edges.

## Solution

Reference implementation from [solution.py on GitHub](https://github.com/wislertt/leetcode-py/blob/main/leetcode/number_of_connected_components_in_an_undirected_graph/solution.py), full suite in [test\_solution.py](https://github.com/wislertt/leetcode-py/blob/main/leetcode/number_of_connected_components_in_an_undirected_graph/test_solution.py):

```python theme={"theme":{"light":"github-light","dark":"github-dark"}}
class Solution:
    # Time: O(n + e)
    # Space: O(n + e)
    def count_components(self, n: int, edges: list[list[int]]) -> int:
        # Build adjacency list
        graph: list[list[int]] = [[] for _ in range(n)]
        for u, v in edges:
            graph[u].append(v)
            graph[v].append(u)

        visited = set()
        components = 0

        def dfs(node: int) -> None:
            visited.add(node)
            for neighbor in graph[node]:
                if neighbor not in visited:
                    dfs(neighbor)

        # Count connected components
        for i in range(n):
            if i not in visited:
                dfs(i)
                components += 1

        return components
```

## Complexity

| Time     | Space    |
| -------- | -------- |
| O(n + e) | O(n + e) |

## Tags

[Grind](/catalog/grind), [Blind 75](/catalog/blind-75), [NeetCode 150](/catalog/neetcode-150), [NeetCode 250](/catalog/neetcode-250), [NeetCode All](/catalog/neetcode).