323. Number of Connected Components in an Undirected Graph
Number of Connected Components in an Undirected Graph (LeetCode 323) is a Medium Data Structures and Algorithms interview problem you can solve, run and submit on Thita.ai. It belongs to the Graph Traversal Patterns (DFS & BFS) pattern, in the Union-Find (Disjoint Set Union - DSU) subpattern.
How to solve Number of Connected Components in an Undirected Graph
Number of Connected Components in an Undirected Graph is a Union-Find problem, part of Graph Traversal Patterns (DFS & BFS). Master Union-Find data structure with path compression and union by rank for connectivity problems.
Work towards the solution in these steps:
- Think about how you can represent the graph connections efficiently to explore their relationships.
- Consider using graph traversal algorithms like DFS or BFS to explore all nodes reachable from a given node.
- How can you keep track of which nodes have been visited to avoid counting the same component multiple times?
The reference solution runs in O(E + N) time and O(N) space.
The Number of Connected Components in an Undirected Graph solution and editorial walks through the full approach with reference code.
Problem statement
You are given an integer n representing the number of nodes in an undirected graph, labeled from 0 to n - 1. You are also given a 2D array edges, where each edges[i] = [ai, bi] indicates that there is an undirected edge between nodes ai and bi.
Return the number of connected components in the graph.
Constraints: - 1 <= n <= 2000 - 0 <= edges.length <= n (n - 1) / 2 - edges[i].length == 2 - 0 <= ai, bi < n - ai != bi - There are no repeated edges.
Examples
Example 1
Input: {"n": 5, "edges": [[0, 1], [1, 2], [3, 4]]}
Output: 2
Explanation: There are two connected components: [0,1,2] and [3,4].
Example 2
Input: {"n": 4, "edges": [[0, 1], [1, 2], [2, 3]]}
Output: 1
Explanation: All nodes are connected in a chain, so only one connected component.
Topics and companies
Topics: Depth-First Search, Breadth-First Search, Union Find, Graph.
Reported in interviews at Amazon, Facebook, LinkedIn, Microsoft, Apple.
How to practise Number of Connected Components in an Undirected Graph on Thita.ai
Starter code is provided in C#, C++, Go, Java, JavaScript and Python. Your solution runs against 5 test cases for this problem, with the AI coach available for a hint when you are stuck rather than a finished answer. The reference solution runs in O(E + N) time and O(N) space.
Open Number of Connected Components in an Undirected Graph in the code editor, or read the Number of Connected Components in an Undirected Graph editorial for a worked solution with its approach and complexity analysis.
Where Number of Connected Components in an Undirected Graph sits in the DSA pattern sheet
- Graph Traversal Patterns (DFS & BFS) pattern guide
- Union-Find (Disjoint Set Union - DSU) subpattern
- The full DSA patterns sheet
Problems related to Number of Connected Components in an Undirected Graph
Other problems that use the same Union-Find (Disjoint Set Union - DSU) and Graph Traversal Patterns (DFS & BFS) techniques:
- Accounts Merge — Medium, same subpattern
- Graph Valid Tree — Medium, same subpattern
- Greatest Common Divisor Traversal — Hard, same subpattern
- Largest Component Size by Common Factor — Hard, same subpattern
- Most Stones Removed with Same Row or Column — Medium, same subpattern
- Number of Islands II — Hard, same subpattern
Number of Connected Components in an Undirected Graph FAQ
What is the LeetCode number of Number of Connected Components in an Undirected Graph?
Number of Connected Components in an Undirected Graph is LeetCode problem 323, rated Medium.
What pattern is used to solve Number of Connected Components in an Undirected Graph?
Number of Connected Components in an Undirected Graph is a Union-Find problem. It belongs to the Graph Traversal Patterns (DFS & BFS) pattern, in the Union-Find (Disjoint Set Union - DSU) subpattern.
What is the time complexity of Number of Connected Components in an Undirected Graph?
The reference solution runs in O(E + N) time and O(N) space.
Which companies ask Number of Connected Components in an Undirected Graph?
Number of Connected Components in an Undirected Graph has been reported in interviews at Amazon, Facebook, LinkedIn, Microsoft, Apple.