Number of Connected Components

▶

Steps

setup

Build adjacency list

The algorithm constructs the adjacency list from the input edges, representing the graph connections for efficient traversal.

💡 Building the adjacency list is essential to quickly find neighbors of each node during BFS.

Line:

graph = defaultdict(list)
for u, v in edges:
    graph[u].append(v)
    graph[v].append(u)

💡 The graph structure is now ready for traversal, with each node linked to its neighbors.

traverse

Start BFS from node 0

The algorithm begins BFS from node 0 because it is unvisited, adding it to the queue and marking it visited.

💡 Starting BFS from an unvisited node discovers a new connected component.

Line:

for i in range(n):
    if i not in visited:
        queue = deque([i])
        visited.add(i)

💡 This step initiates exploration of the first connected component containing node 0.

traverse

Process node 0

Node 0 is dequeued for processing. The algorithm will explore its neighbors to discover more nodes in this component.

💡 Processing a node means exploring its neighbors to find connected nodes.

Line:

node = queue.popleft()

💡 Node 0 is now the current node being explored.

traverse

Explore neighbor 1 of node 0

The algorithm examines neighbor 1 of node 0. Since 1 is unvisited, it is marked visited and added to the queue.

💡 Discovering unvisited neighbors expands the current connected component.

Line:

for neighbor in graph[node]:
    if neighbor not in visited:
        visited.add(neighbor)
        queue.append(neighbor)

💡 This step shows how BFS discovers new nodes connected to the current node.

traverse

Process node 1

Node 1 is dequeued and marked as processing. The algorithm will explore its neighbors next.

💡 Processing node 1 continues BFS exploration within the current component.

Line:

node = queue.popleft()

💡 Node 1 is now the active node being explored.

traverse

Explore neighbor 0 of node 1

Neighbor 0 of node 1 is checked but already visited, so it is skipped.

💡 Skipping visited neighbors prevents cycles and redundant processing.

Line:

for neighbor in graph[node]:
    if neighbor not in visited:

💡 BFS avoids revisiting nodes, ensuring efficient traversal.

traverse

Explore neighbor 2 of node 1

Neighbor 2 of node 1 is unvisited, so it is marked visited and added to the queue.

💡 Discovering new neighbors expands the BFS frontier within the component.

Line:

if neighbor not in visited:
    visited.add(neighbor)
    queue.append(neighbor)

💡 BFS continues to discover all nodes connected to the starting node.

traverse

Process node 2

Node 2 is dequeued and marked processing to explore its neighbors.

💡 Processing node 2 continues BFS to ensure all connected nodes are visited.

Line:

node = queue.popleft()

💡 Node 2 is now the active node being explored.

traverse

Explore neighbor 1 of node 2

Neighbor 1 of node 2 is already visited, so it is skipped.

💡 Skipping visited neighbors prevents revisiting nodes and infinite loops.

Line:

for neighbor in graph[node]:
    if neighbor not in visited:

💡 BFS ensures each node is processed once.

traverse

Finish BFS for component 1

No more neighbors to explore from node 2, BFS queue is empty, so the first connected component is fully discovered. Increment component count to 1.

💡 Completing BFS for one component ensures all its nodes are visited before moving on.

Line:

count += 1

💡 One connected component has been fully explored.

traverse

Start BFS from node 3

Node 3 is unvisited, so BFS starts from node 3, marking it visited and adding it to the queue to explore the second component.

💡 Starting BFS from another unvisited node finds a new connected component.

Line:

if i not in visited:
    queue = deque([i])
    visited.add(i)

💡 The algorithm detects the second connected component starting at node 3.

traverse

Process node 3

Node 3 is dequeued and marked processing to explore its neighbors in the second component.

💡 Processing node 3 begins exploration of the second connected component.

Line:

node = queue.popleft()

💡 Node 3 is now the active node being explored.

traverse

Explore neighbor 4 of node 3

Neighbor 4 of node 3 is unvisited, so it is marked visited and added to the queue.

💡 Discovering neighbor 4 expands the second connected component.

Line:

if neighbor not in visited:
    visited.add(neighbor)
    queue.append(neighbor)

💡 BFS continues to discover all nodes in the second component.

traverse

Process node 4

Node 4 is dequeued and marked processing to explore its neighbors.

💡 Processing node 4 continues BFS to complete the second component.

Line:

node = queue.popleft()

💡 Node 4 is now the active node being explored.

traverse

Explore neighbor 3 of node 4

Neighbor 3 of node 4 is already visited, so it is skipped.

💡 Skipping visited neighbors prevents redundant processing and infinite loops.

Line:

for neighbor in graph[node]:
    if neighbor not in visited:

💡 BFS processes each node once, ensuring efficiency.

traverse

Finish BFS for component 2

No more neighbors to explore from node 4, BFS queue is empty, so the second connected component is fully discovered. Increment component count to 2.

💡 Completing BFS for the second component ensures all nodes are visited.

Line:

count += 1

💡 Two connected components have been fully explored.

traverse

Check remaining nodes 4

Node 4 is already visited, so BFS is not started again. The algorithm finishes checking all nodes.

💡 Skipping visited nodes avoids redundant BFS calls.

Line:

for i in range(n):
    if i not in visited:

💡 All nodes have been processed, so BFS ends.

reconstruct

Return final count

The algorithm returns the total count of connected components, which is 2.

💡 Returning the count completes the algorithm, summarizing the BFS discoveries.

Line:

return count

💡 The graph contains exactly two connected components.

from collections import defaultdict, deque

def countComponents(n, edges):
    graph = defaultdict(list)  # STEP 1
    for u, v in edges:  # STEP 1
        graph[u].append(v)
        graph[v].append(u)

    visited = set()  # STEP 2
    count = 0

    for i in range(n):  # STEP 2
        if i not in visited:  # STEP 3
            queue = deque([i])  # STEP 3
            visited.add(i)  # STEP 3
            while queue:  # STEP 4
                node = queue.popleft()  # STEP 4
                for neighbor in graph[node]:  # STEP 4
                    if neighbor not in visited:  # STEP 4
                        visited.add(neighbor)  # STEP 4
                        queue.append(neighbor)  # STEP 4
            count += 1  # STEP 10 & 16
    return count  # STEP 18

if __name__ == '__main__':
    n = 5
    edges = [[0,1],[1,2],[3,4]]
    print(countComponents(n, edges))  # Output: 2

📊

Number of Connected Components - Watch the Algorithm Execute, Step by Step

Watching the BFS traversal step-by-step reveals how nodes are grouped into connected components and how the algorithm avoids revisiting nodes, which is hard to grasp from code alone.

Visiting: none

0

1

2

3

4

Visiting: none

0

1

2

3

4

Queue / Stack

0

Visiting: 0

0

1

2

3

4

Visiting: 0

Edge: 0 → 1

0

1

2

3

4

Queue / Stack

1

Visiting: 1

0

1

2

3

4

Visiting: 1

Edge: 1 → 0

0

1

2

3

4

Visiting: 1

Edge: 1 → 2

0

1

2

3

4

Queue / Stack

2

Visiting: 2

0

1

2

3

4

Visiting: 2

Edge: 2 → 1

0

1

2

3

4

Visiting: none

0

1

2

3

4

Visiting: none

0

1

2

3

4

Queue / Stack

3

Visiting: 3

0

1

2

3

4

Visiting: 3

Edge: 3 → 4

0

1

2

3

4

Queue / Stack

4

Visiting: 4

0

1

2

3

4

Visiting: 4

Edge: 4 → 3

0

1

2

3

4

Visiting: none

0

1

2

3

4

Visiting: none

0

1

2

3

4

Visiting: none

0

1

2

3

4

Key Takeaways

✓ BFS traversal groups nodes into connected components by exploring all reachable nodes from an unvisited start node.

This grouping is hard to see from code alone but becomes clear when watching BFS queue and visited states change.

✓ The queue in BFS ensures nodes are processed in layers, which guarantees all nodes in a component are discovered before moving to the next.

Visualizing the queue contents reveals BFS's layer-by-layer exploration order.

✓ Skipping already visited neighbors prevents infinite loops and redundant work, ensuring BFS efficiency.

Seeing the algorithm skip visited nodes during traversal clarifies how BFS avoids cycles.

Practice

1. You are given a 2D grid of 0s and 1s. For each cell containing 1, you need to find the distance to the nearest 0. Which algorithmic approach guarantees the shortest distance for all cells efficiently?

easy

A. Use a multi-source Breadth-First Search (BFS) starting from all 0s simultaneously.

B. Run a Depth-First Search (DFS) from each 1 to find the nearest 0.

C. Apply a greedy approach updating distances by scanning rows and columns once.

D. Use a brute force approach checking every cell independently for nearest 0.

Solution

1. Step 1: Understand the problem constraints

   We need shortest distances from each 1 to the nearest 0 in a grid, which is a shortest path problem on an unweighted graph.

2. Step 2: Identify the correct algorithm

   Multi-source BFS starting from all 0s simultaneously guarantees shortest distances because BFS explores neighbors in increasing order of distance.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Multi-source BFS ensures shortest path in O(m*n) time [OK]

Hint: Shortest path in grid with multiple sources -> multi-source BFS [OK]

Common Mistakes:

• Using DFS which does not guarantee shortest path
• Greedy scanning misses some paths
• Brute force is too slow

2. Consider the following Python code implementing the optimal solution for the minimum effort path problem. Given the input heights = [[1,2,2],[3,8,2],[5,3,5]], what is the final returned minimum effort?

easy

A. 2

B. 1

C. 3

D. 4

Solution

1. Step 1: Trace initial steps

   Start at (0,0) with effort 0. From (0,0), neighbors are (1,0) with effort max(0,|1-3|)=2 and (0,1) with effort max(0,|1-2|)=1.

2. Step 2: Explore paths and update efforts

   Heap pops (0,0,1) with effort 1, then explores neighbors updating efforts. The minimal maximum effort path found is 2.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Manual tracing confirms minimal effort is 2 [OK]

Hint: Trace heap pops and max edge efforts [OK]

Common Mistakes:

• Confusing sum of differences with max difference
• Off-by-one in indices
• Returning effort before reaching target

3. What is the time complexity of the optimal algorithm that finds the minimum number of vertices to reach all nodes in a directed acyclic graph with n nodes and e edges?

medium

A. O(n * e) because each node is processed for all edges

B. O(n + e) because each node and edge is processed once

C. O(n^2) because of nested loops over nodes

D. O(e log n) due to priority queue operations in topological sort

Solution

1. Step 1: Identify loops in the algorithm

   The algorithm iterates over all edges once to build the graph and in-degree array, then processes each node and its edges once during the queue processing.

2. Step 2: Combine complexities

   Building graph: O(e), processing nodes and edges in BFS: O(n + e). No nested loops over all nodes and edges.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Linear time in nodes and edges for DAG traversal [OK]

Hint: Topological sort runs in O(n + e) time [OK]

Common Mistakes:

• Assuming nested loops cause O(n*e)
• Confusing with dense graph complexities
• Thinking priority queues are used

4. Suppose the course prerequisites can include self-dependencies (a course requiring itself) and multiple edges between the same courses. Which modification to the Kahn's Algorithm is necessary to correctly detect cycles in this scenario?

hard

A. Ignore self-loops and treat multiple edges as one; no algorithm change needed.

B. Use DFS with coloring instead of Kahn's Algorithm because BFS cannot detect self-loops.

C. Modify in-degree initialization to count self-loops and multiple edges correctly.

D. Add a check to detect self-loops explicitly before running Kahn's Algorithm.

Solution

1. Step 1: Understand impact of self-loops and multiple edges

   Self-loops increase in-degree of a node, and multiple edges increase in-degree counts accordingly.

2. Step 2: Modify in-degree initialization to count all edges accurately

   Counting all edges including self-loops ensures Kahn's Algorithm correctly identifies cycles by never reducing in-degree to zero for cyclic nodes.

3. Step 3: Confirm no other algorithm change needed

   Algorithm logic remains the same; accurate in-degree counts handle these cases.

4. Final Answer:

   Option C -> Option C

5. Quick Check:

   Proper in-degree counts detect cycles including self-loops [OK]

Hint: Count all edges correctly to detect cycles including self-loops [OK]

Common Mistakes:

• Ignoring self-loops leads to false positives
• Assuming BFS cannot detect self-loops
• Treating multiple edges as single edge incorrectly

5. Suppose the problem changes: fresh oranges can become rotten multiple times, and rot can spread back to previously rotten oranges if it results in a faster rot time. Which modification to the DFS-based solution correctly handles this scenario?

hard

A. Switch to a brute force simulation updating the grid minute by minute until no changes

B. Keep the original DFS with pruning but run it multiple times until no updates occur

C. Use a multi-source BFS but do not track times, just mark visited once

D. Remove the pruning condition that skips DFS if time_grid[r][c] <= time, allowing revisits with better times

Solution

1. Step 1: Understand new rot dynamics

   Rot can improve previously recorded rot times, so pruning based on time_grid[r][c] <= time is invalid.

2. Step 2: Modify DFS to allow revisits with better times

   Removing pruning condition enables DFS to update time_grid when a faster rot path is found.

3. Step 3: Confirm correctness

   This ensures all cells have minimum rot times even if rot spreads back to previously rotten oranges.

4. Final Answer:

   Option D -> Option D

5. Quick Check:

   Allowing revisits with better times handles dynamic rot spread correctly [OK]

Hint: Allow revisits if they improve rot time [OK]

Common Mistakes:

• Keeping pruning causes stale times
• Using BFS without time tracking
• Brute force is inefficient