Number of Connected Components

📋

Problem

Imagine a social network where you want to find how many friend groups exist - groups where everyone is connected directly or indirectly.

Given an undirected graph with n nodes labeled from 0 to n-1 and a list of edges where each edge connects two nodes, return the number of connected components in the graph.

1 ≤ n ≤ 10^50 ≤ edges.length ≤ 10^5edges[i].length == 20 ≤ edges[i][0], edges[i][1] < nNo duplicate edgesNo self-loops

Edge cases: n = 1, edges = [] → 1 (single node is one component)n = 3, edges = [] → 3 (no edges, all nodes isolated)n = 4, edges = [[0,1],[2,3]] → 2 (two pairs of connected nodes)

</>

IDE

def countComponents(n: int, edges: list[list[int]]) -> int:public int countComponents(int n, int[][] edges)int countComponents(int n, vector<vector<int>>& edges)function countComponents(n, edges)

def countComponents(n, edges):
    # Write your solution here
    pass

class Solution {
    public int countComponents(int n, int[][] edges) {
        // Write your solution here
        return 0;
    }
}

#include <vector>
using namespace std;

int countComponents(int n, vector<vector<int>>& edges) {
    // Write your solution here
    return 0;
}

function countComponents(n, edges) {
    // Write your solution here
}

Common Bugs to Avoid

Wrong: 0Code returns 0 for empty or single node graphs incorrectly.✅ Add base case: if n == 0 return 0; if edges empty return n.

Wrong: 1Code treats all nodes as connected even when disconnected.✅ Ensure DFS or union-find only counts connected nodes per component, increment count per unvisited node.

Wrong: 3Code counts self-loops as separate components or errors on self-loops.✅ Ignore edges where u == v when building graph or union-find.

Wrong: Less than expectedIsolated nodes not counted as separate components.✅ Initialize count to n and decrement only when union merges sets.

Wrong: Timeout or no outputUsing exponential DFS without pruning or inefficient data structures.✅ Use adjacency list and iterative DFS or union-find with path compression for O(n+e) complexity.

✓

Test Cases

Focus on handling graphs with no edges and single nodes correctly.

Consider tricky cases like cycles, isolated nodes, and self-loops.

Optimize your solution to run efficiently on large graphs using union-find or iterative DFS.

t1_01basic

Input{"n":5,"edges":[[0,1],[1,2],[3,4]]}

Expected2

⏱ Performance - must finish in 2000ms

There are two connected components: {0,1,2} and {3,4}.

💡 Think about how to traverse all nodes and mark connected ones.

💡 Use DFS or Union-Find to group connected nodes and count groups.

💡 Count how many times you start a DFS or Union-Find union operation on unvisited nodes.

Why it failed: Incorrect count means you likely missed marking all connected nodes or incorrectly counted components. Fix by ensuring DFS/Union-Find visits all connected nodes before incrementing count.

✓ Correctly counts connected components using graph traversal or union-find.

t1_02basic

Input{"n":4,"edges":[[0,1],[2,3]]}

Expected2

⏱ Performance - must finish in 2000ms

Two connected components: {0,1} and {2,3}.

💡 Check how your algorithm handles multiple disconnected pairs.

💡 Verify that each connected group is counted exactly once.

💡 Ensure your visited set or union-find structure correctly tracks all nodes.

Why it failed: If output is not 2, you may be double counting or missing components. Fix by properly marking visited nodes or union-find parents.

✓ Correctly identifies multiple disconnected components.

t2_01edge

Input{"n":0,"edges":[]}

Expected0

⏱ Performance - must finish in 2000ms

No nodes means no connected components.

💡 Consider the case when there are no nodes at all.

💡 Your code should handle n=0 gracefully without errors.

💡 Return 0 immediately if n=0 since no components exist.

Why it failed: Returning non-zero means code does not handle empty graph correctly. Fix by adding a base case for n=0 returning 0.

✓ Correctly returns 0 for empty graph input.

t2_02edge

Input{"n":1,"edges":[]}

Expected1

⏱ Performance - must finish in 2000ms

Single node with no edges forms one component.

💡 A single node alone is a connected component.

💡 Ensure your code counts isolated nodes as components.

💡 If no edges, count should equal number of nodes.

Why it failed: Returning 0 means isolated nodes are not counted. Fix by initializing count to n and decrementing only when unions happen.

✓ Correctly counts isolated single node as one component.

t2_03edge

Input{"n":3,"edges":[]}

Expected3

⏱ Performance - must finish in 2000ms

Three isolated nodes, each is its own component.

💡 No edges means all nodes are disconnected.

💡 Count should be equal to number of nodes when edges are empty.

💡 Verify your code does not assume edges exist to count components.

Why it failed: Returning less than n means isolated nodes are ignored. Fix by counting all nodes as separate components if no edges connect them.

✓ Correctly counts all isolated nodes as separate components.

t3_01corner

Input{"n":5,"edges":[[0,1],[1,2],[2,3],[3,4]]}

Expected1

⏱ Performance - must finish in 2000ms

All nodes connected in a chain forming a single component.

💡 Check if your algorithm correctly merges chains of nodes.

💡 Verify that transitive connections are considered in your traversal or union-find.

💡 Ensure union-find unions all connected nodes, not just direct neighbors.

Why it failed: Output > 1 means your code treats connected chain as multiple components. Fix by ensuring union/find or DFS visits all reachable nodes.

✓ Correctly identifies a single connected component in a chain.

t3_02corner

Input{"n":6,"edges":[[0,1],[1,2],[3,4]]}

Expected3

⏱ Performance - must finish in 2000ms

Three components: {0,1,2}, {3,4}, and isolated node {5}.

💡 Check if isolated nodes are counted as separate components.

💡 Verify your code handles nodes with no edges correctly.

💡 Ensure union-find or DFS includes all nodes in counting.

Why it failed: Output less than 3 means isolated nodes ignored. Fix by initializing count to n and decrementing only on unions.

✓ Correctly counts isolated nodes as separate components.

t3_03corner

Input{"n":4,"edges":[[0,1],[1,2],[2,0],[3,3]]}

Expected2

⏱ Performance - must finish in 2000ms

Cycle among nodes 0,1,2 forms one component; node 3 isolated (self-loop ignored).

💡 Self-loops do not affect component count.

💡 Check if your code ignores or mishandles self-loops.

💡 Ensure your graph construction excludes self-loops as per constraints.

Why it failed: Counting self-loop as separate component or error means self-loops not ignored. Fix by skipping edges where u == v.

✓ Correctly ignores self-loops and counts components.

t4_01performance

Input{"_description":"n=100000 at constraint boundary - executor generates this"}

Expectednull

⏱ Performance - must finish in 2000ms

Input size n=100000 with up to 100000 edges; solution must run in O(n+e) time within 2 seconds.

💡 Use efficient graph traversal or union-find with path compression.

💡 Avoid recursion depth issues by using iterative DFS or union-find.

💡 Optimize data structures to achieve near-linear time complexity.

Why it failed: TLE indicates algorithm is not O(n+e) or uses exponential/inefficient approach. Fix by implementing union-find or iterative DFS with adjacency list.

✓ Algorithm runs efficiently in O(n+e) time confirming scalability.

Practice

1. You are given an undirected graph and need to determine if its vertices can be divided into two groups such that no edge connects vertices within the same group. Which algorithmic approach guarantees an efficient and correct solution for this problem?

easy

A. Greedy algorithm that assigns groups based on vertex degree

B. Dynamic Programming on subsets of vertices to find valid partitions

C. Depth-First Search (DFS) to find cycles and count their lengths

D. Breadth-First Search (BFS) coloring to assign two colors and check for conflicts

Solution

1. Step 1: Understand the problem as a 2-coloring challenge

   The problem requires checking if the graph is bipartite, which means it can be colored using two colors such that no adjacent vertices share the same color.

2. Step 2: Identify BFS coloring as the optimal approach

   BFS coloring systematically assigns colors level by level and detects conflicts efficiently, guaranteeing correctness and linear time complexity.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   BFS coloring is the standard method for bipartite checking [OK]

Hint: BFS coloring detects bipartite conflicts efficiently [OK]

Common Mistakes:

• Assuming greedy degree-based grouping works
• Confusing cycle detection with bipartite check

2. Consider the following Python code implementing bidirectional BFS to find the shortest path in a binary matrix. Given the input grid below, what is the returned shortest path length?

grid = [
  [0, 1, 0],
  [1, 0, 0],
  [1, 1, 0]
]

# Code snippet uses the bidirectional BFS approach as described.

What is the output of shortestPathBinaryMatrix(grid)?

easy

A. 3

B. 5

C. -1

D. 4

Solution

1. Step 1: Trace BFS from start (0,0)

   Start at (0,0) with distance 1. Neighbors reachable: (1,1) at distance 2.

2. Step 2: Trace BFS from end (2,2)

   Start at (2,2) with distance 1. Neighbors reachable: (1,2) at distance 2, (1,1) at distance 2.

3. Step 3: Meeting point

   Both searches meet at (1,1). Sum distances: 2 (start side) + 2 (end side) = 4, but since both include the meeting cell, shortest path length is 3.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   Shortest path length is 3 steps [OK]

Hint: Bidirectional BFS meets in middle, sum distances minus 1 [OK]

Common Mistakes:

• Off-by-one in path length
• Ignoring meeting cell counted twice

3. What is the time complexity of the optimal approach using a single trust score array to find the town judge, given n people and m trust pairs?

medium

A. O(n * m) because we scan trust pairs for each person

B. O(n^2) because we check trust relationships pairwise

C. O(m^2) because trust pairs are nested in loops

D. O(n + m) because we process each trust pair once and then scan all people once

Solution

1. Step 1: Identify loops in the algorithm

   The algorithm iterates once over all trust pairs (m) and then once over all people (n).

2. Step 2: Combine complexities

   Processing trust pairs is O(m), scanning people is O(n), total O(n + m).

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Single pass over trust and people arrays [OK]

Hint: Single pass over trust pairs and people yields O(n + m) [OK]

Common Mistakes:

• Assuming nested loops cause O(n*m)
• Confusing trust pairs count with people count
• Ignoring linear scans after trust processing

4. The following code attempts to check if a graph is a valid tree. Which line contains a subtle bug that can cause incorrect results on disconnected graphs?

medium

A. Line checking if edge count equals n - 1

B. Line returning true without verifying all nodes visited

C. Line skipping neighbor if it equals parent

D. Line adding neighbor to queue

Solution

1. Step 1: Identify final return condition

   The code returns true without checking if all nodes were visited, missing disconnected components.

2. Step 2: Understand impact

   Disconnected graphs with correct edge count and no cycles will incorrectly return true.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Must verify visited nodes count equals n [OK]

Hint: Always check all nodes visited for connectivity [OK]

Common Mistakes:

• Forgetting connectivity check after BFS/DFS
• Misinterpreting cycle detection as full validation

5. Suppose the graph may contain cycles. Which modification to the optimal algorithm is necessary to correctly find the minimal set of vertices to reach all nodes?

hard

A. Run the same topological sort algorithm; cycles do not affect the result.

B. Use BFS from each node to find reachability since topological sort fails.

C. Ignore in-degree and pick nodes with maximum out-degree instead.

D. Detect cycles first and return an error or handle strongly connected components.

Solution

1. Step 1: Understand cycle impact

   Topological sort requires DAGs; cycles prevent valid ordering and break the algorithm.

2. Step 2: Modify approach

   Detect cycles using DFS or union-find. For cyclic graphs, identify strongly connected components and treat them as single nodes or return error.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Cycle detection is essential before topological sort [OK]

Hint: Topological sort requires DAG; detect cycles first [OK]

Common Mistakes:

• Assuming topological sort works on cyclic graphs
• Ignoring cycles and returning incorrect minimal sets
• Using BFS from each node which is inefficient