What is the time complexity of LeetCode 323. Number of Connected Components in an Undirected Graph?

The Python solution on this page runs in O(n + m).

What is the space complexity of LeetCode 323. Number of Connected Components in an Undirected Graph?

The Python solution on this page uses O(n + m) auxiliary space.

Number of Connected Components in an Undirected Graph — LeetCode 323 Python Solution

MediumLeetCode PremiumDepth-First SearchBreadth-First SearchUnion FindGraph

Problem: #323
Pattern: Union-Find
Reading time: 3 min
Source: leetcode.com

The problem

You have a graph of n nodes. You are given an integer n and an array edges where edges[i] = [ai, bi] indicates that there is an edge between ai and bi in the graph.

Example

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

Python solution

Python

class Solution:
    def countComponents(self, n: int, edges: List[List[int]]) -> int:
        def dfs(i: int) -> int:
            if i in vis:
                return 0
            vis.add(i)
            for j in g[i]:
                dfs(j)
            return 1

        g = [[] for _ in range(n)]
        for a, b in edges:
            g[a].append(b)
            g[b].append(a)
        vis = set()
        return sum(dfs(i) for i in range(n))

Complexity

Measure	Complexity
Time	O(n + m)
Space	O(n + m) auxiliary

Pattern: Union-Find

Merge groups and ask whether two things are connected, both in near-constant time. LeetCode 323. Number of Connected Components in an Undirected Graph is filed here because LeetCode tags it Union Find, which is the vocabulary this hub collects.

The union-find guide has the Python template for the pattern and the 83 LeetCode problems that use it.

On study lists

This problem is on Blind 75 and NeetCode 150.

Frequently asked questions

How hard is LeetCode 323. Number of Connected Components in an Undirected Graph?: LeetCode 323. Number of Connected Components in an Undirected Graph is rated Medium on LeetCode.
What is the time complexity of LeetCode 323. Number of Connected Components in an Undirected Graph?: The Python solution on this page runs in O(n + m).
What is the space complexity of LeetCode 323. Number of Connected Components in an Undirected Graph?: The Python solution on this page uses O(n + m) auxiliary space.
What topics does LeetCode 323. Number of Connected Components in an Undirected Graph cover?: LeetCode 323. Number of Connected Components in an Undirected Graph is tagged Depth-First Search, Breadth-First Search, Union Find and Graph on LeetCode.
Is LeetCode 323. Number of Connected Components in an Undirected Graph a premium problem?: Yes. LeetCode 323. Number of Connected Components in an Undirected Graph is a LeetCode Premium problem, so the full statement and test cases require a paid LeetCode subscription.