Back to Problems

Number of Connected Components in an Undirected Graph

Medium
Union Find

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.

Return the number of connected components in the graph.

Connected Component Definition: A connected component is a maximal set of nodes such that there is a path between every pair of nodes in the set.

Union Find Approach:

  1. Initialize n sets (each node is its own component)
  2. For each edge (a, b), union the sets containing a and b
  3. Count the number of distinct roots

Key Insight: Each union operation reduces the component count by 1 (when merging different components). Start with n components and track how many successful unions occur.

Time Complexity: O(E * alpha(N)) where alpha is the inverse Ackermann function (effectively O(E) for practical purposes).

Example 1

Input: n = 5, edges = [[0,1],[1,2],[3,4]]
Output: 2
Explanation: Component 1: {0, 1, 2}. Component 2: {3, 4}. Total: 2 components.

Example 2

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

Example 3

Input: n = 5, edges = []
Output: 5
Explanation: No edges means no connections. Each node is its own component. Total: 5 components.

Constraints

  • •1 <= n <= 2000
  • •0 <= edges.length <= 5000
  • •edges[i].length == 2
  • •0 <= ai, bi < n
  • •ai != bi
  • •There are no repeated edges.
Show Hints (4)
Hint 1: Start by assuming each node is its own connected component. How many components do you start with?
Hint 2: When you process an edge connecting nodes a and b, what happens to the component count?
Hint 3: If a and b are already in the same component, does processing the edge (a, b) change anything?
Hint 4: Think about it this way: start with n components, subtract 1 for each edge that actually merges two different components.
Loading editor...

Test Results

Click "Run" to execute your code against test cases

AI Tutor

Socratic guidance - I'll ask questions, not give answers

AI Tutor
Hello! I'm your AI tutor, here to guide you through this problem using the Socratic method. I won't give you direct answers, but I'll ask questions and provide hints to help you discover the solution yourself. What's your first instinct when you look at this problem? What approach comes to mind?