Connected Components Using BFS in DSA C++ - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to declare the adjacency list for the graph.

DSA C++

vector<vector<int>> graph([1]);

Drag options to blanks, or click blank then click option'

An

Bvisited

Cedges

Dqueue

Attempts:

3 left

💡 Hint

Common Mistakes

Using edges count instead of nodes count for adjacency list size.

Using variable names unrelated to graph size.

The adjacency list is a vector of vectors sized by the number of nodes n.

2fill in blank

medium

Complete the code to mark a node as visited inside BFS.

DSA C++

visited[[1]] = true;

Drag options to blanks, or click blank then click option'

Astart

Bqueue

Cneighbor

Dnode

Attempts:

3 left

💡 Hint

Common Mistakes

Marking the neighbor instead of the current node.

Using the queue variable instead of node index.

We mark the current node as visited to avoid revisiting it.

3fill in blank

hard

Fix the error in the BFS loop condition to process nodes until the queue is empty.

DSA C++

while (![1].empty()) {

Drag options to blanks, or click blank then click option'

Aqueue

Bgraph

Cvisited

Dneighbors

Attempts:

3 left

💡 Hint

Common Mistakes

Checking if visited is empty instead of queue.

Using graph or neighbors which are not queues.

The BFS loop continues while the queue has nodes to process.

4fill in blank

hard

Fill both blanks to add neighbors to the queue if not visited.

DSA C++

for (int [1] : graph[node]) {
    if (!visited[[2]]) {
        queue.push([2]);
        visited[[2]] = true;
    }
}

Drag options to blanks, or click blank then click option'

Aneighbor

Bnode

Cvisited

Dqueue

Attempts:

3 left

💡 Hint

Common Mistakes

Using node instead of neighbor in the loop.

Marking visited or queue variables incorrectly.

We iterate over each neighbor of the current node and add it to the queue if not visited.

5fill in blank

hard

Fill all three blanks to count connected components using BFS.

DSA C++

int count = 0;
for (int i = 0; i < [1]; i++) {
    if (!visited[i]) {
        queue.push(i);
        visited[i] = true;
        while (!queue.[2]()) {
            int node = queue.front();
            queue.[3]();
            for (int neighbor : graph[node]) {
                if (!visited[neighbor]) {
                    queue.push(neighbor);
                    visited[neighbor] = true;
                }
            }
        }
        count++;
    }
}

Drag options to blanks, or click blank then click option'

An

Bempty

Cpop

Dsize

Attempts:

3 left

💡 Hint

Common Mistakes

Using wrong variable for loop limit.

Using wrong queue methods for checking and popping.

We loop over all n nodes, use queue.empty() to check if BFS continues, and queue.pop() to remove the front node.

Practice

1. What does the BFS algorithm help find in an undirected graph when used for connected components?

easy

A. The total number of edges in the graph

B. The shortest path between two nodes only

C. The maximum degree of any node in the graph

D. All nodes reachable from a starting node forming one connected component

Solution

1. Step 1: Understand BFS traversal in undirected graph

   BFS explores all nodes reachable from a given start node by visiting neighbors level by level.

2. Step 2: Connect BFS to connected components

   All nodes visited during BFS from a start node belong to the same connected component.

3. Final Answer:

   All nodes reachable from a starting node forming one connected component -> Option D

4. Quick Check:

   BFS finds connected components = All nodes reachable from a starting node forming one connected component [OK]

Hint: BFS visits all nodes in one connected component [OK]

Common Mistakes:

• Confusing BFS with shortest path only
• Thinking BFS counts edges
• Mixing connected components with node degrees

2. Which of the following is the correct way to mark a node as visited in BFS when using a vector<bool> visited in C++?

easy

A. visited[node] = true;

B. visited.push_back(node);

C. visited.insert(node);

D. visited[node] == true;

Solution

1. Step 1: Understand vector<bool> usage for visited nodes

   visited is a boolean vector indexed by node number; marking visited means setting visited[node] to true.

2. Step 2: Identify correct syntax for assignment

   Assigning true to visited[node] is done by visited[node] = true; other options are invalid or comparisons.

3. Final Answer:

   visited[node] = true; -> Option A

4. Quick Check:

   Mark visited with assignment = visited[node] = true; [OK]

Hint: Use assignment (=), not comparison (==), to mark visited [OK]

Common Mistakes:

• Using == instead of = for assignment
• Trying to push_back in a fixed-size vector
• Using insert which is for sets, not vectors

3. Given the following graph represented as adjacency list and BFS code to find connected components, what is the output number of connected components?

int n = 5;
vector adj = {{1}, {0, 2}, {1}, {4}, {3}};
vector<bool> visited(n, false);
int count = 0;
for (int i = 0; i < n; i++) {
  if (!visited[i]) {
    queue<int> q;
    q.push(i);
    visited[i] = true;
    while (!q.empty()) {
      int u = q.front(); q.pop();
      for (int v : adj[u]) {
        if (!visited[v]) {
          visited[v] = true;
          q.push(v);
        }
      }
    }
    count++;
  }
}
cout << count << endl;

medium

A. 1

B. 2

C. 3

D. 4

Solution

1. Step 1: Analyze the graph adjacency list

   Nodes 0,1,2 form one connected component (0 connected to 1, 1 connected to 2). Nodes 3 and 4 form another connected component (3 connected to 4).

2. Step 2: Trace BFS and count connected components

   Start BFS at node 0: visits 0,1,2 (component 1). Next unvisited node is 3: visits 3,4 (component 2). Total components = 2.

3. Final Answer:

   2 -> Option B

4. Quick Check:

   Two connected groups = 2 [OK]

Hint: Count BFS runs on unvisited nodes for connected components [OK]

Common Mistakes:

• Counting edges instead of components
• Not marking visited correctly causing overcount
• Misreading adjacency list connections

4. Identify the bug in this BFS code snippet for counting connected components:

int count = 0;
for (int i = 0; i < n; i++) {
  if (visited[i]) {
    queue<int> q;
    q.push(i);
    visited[i] = true;
    while (!q.empty()) {
      int u = q.front(); q.pop();
      for (int v : adj[u]) {
        if (!visited[v]) {
          visited[v] = true;
          q.push(v);
        }
      }
    }
    count++;
}

medium

A. The condition should be if (!visited[i]) instead of if (visited[i])

B. visited[i] should be set to false before pushing to queue

C. Queue should be declared outside the for loop

D. count++ should be inside the inner while loop

Solution

1. Step 1: Check the condition to start BFS

   The BFS should start only from unvisited nodes, so the condition must be if (!visited[i]). The code incorrectly starts BFS from visited nodes.

2. Step 2: Understand impact of wrong condition

   Starting BFS from visited nodes means some components won't be counted, causing incorrect count.

3. Final Answer:

   The condition should be if (!visited[i]) instead of if (visited[i]) -> Option A

4. Quick Check:

   Start BFS on unvisited nodes = The condition should be if (!visited[i]) instead of if (visited[i]) [OK]

Hint: Start BFS only if node is not visited [OK]

Common Mistakes:

• Starting BFS on visited nodes
• Misplacing count increment inside loop
• Incorrect queue scope causing logic errors

5. You have a graph with 7 nodes and edges: (0-1), (1-2), (3-4), (5-6). Using BFS to find connected components, what is the correct order of BFS starting nodes and the total number of connected components?

hard

A. Start nodes: 0, 1, 3, 5; Total components: 4

B. Start nodes: 0, 2, 4; Total components: 4

C. Start nodes: 0, 3, 5; Total components: 3

D. Start nodes: 1, 3, 5; Total components: 2

Solution

1. Step 1: Identify connected components from edges

   Edges connect nodes into groups: {0,1,2}, {3,4}, {5,6} forming 3 components.

2. Step 2: Determine BFS start nodes

   BFS starts from the smallest unvisited node in each component: 0 for first, 3 for second, 5 for third.

3. Final Answer:

   Start nodes: 0, 3, 5; Total components: 3 -> Option C

4. Quick Check:

   3 components starting at 0,3,5 = Start nodes: 0, 3, 5; Total components: 3 [OK]

Hint: Start BFS at smallest unvisited node per component [OK]

Common Mistakes:

• Counting wrong number of components
• Starting BFS at nodes inside components instead of smallest
• Confusing edges with components count