Connected Components Using BFS in DSA C++ - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is a connected component in an undirected graph?

A connected component is a group of nodes where each node is reachable from any other node in the same group by following edges.

beginner

How does BFS help in finding connected components?

BFS explores all nodes reachable from a starting node. By running BFS from unvisited nodes, we find all nodes in one connected component before moving to the next.

beginner

What data structure is commonly used to keep track of nodes to visit in BFS?

A queue is used to keep track of nodes to visit in BFS, ensuring nodes are explored in the order they are discovered.

beginner

Why do we mark nodes as visited during BFS?

Marking nodes as visited prevents revisiting the same node multiple times, avoiding infinite loops and repeated work.

intermediate

What is the time complexity of finding connected components using BFS in a graph with V vertices and E edges?

The time complexity is O(V + E) because BFS visits every vertex and edge once.

What does BFS use to keep track of nodes to visit next?

A Queue

B Stack

C Set

D Array

BFS uses a queue to explore nodes in the order they are discovered.

When finding connected components, what do you do after BFS finishes from one node?

A Start BFS from another unvisited node

B Stop the algorithm

C Remove all edges

D Mark all nodes as visited

After BFS finishes one component, start BFS from another unvisited node to find the next component.

What is a connected component in a graph?

A A node with no edges

B A node connected to itself

C A cycle in the graph

D A group of nodes all connected to each other

A connected component is a group of nodes where each node can reach any other node in the group.

Why do we mark nodes as visited in BFS?

A To count nodes

B To avoid revisiting nodes

C To sort nodes

D To delete nodes

Marking nodes as visited prevents revisiting and infinite loops.

What is the time complexity of BFS for connected components in terms of vertices (V) and edges (E)?

A O(V^2)

B O(E^2)

C O(V + E)

D O(log V)

BFS visits each vertex and edge once, so time complexity is O(V + E).

Explain step-by-step how BFS can be used to find all connected components in an undirected graph.

Think about how BFS explores nodes layer by layer and how to find separate groups.

Describe why marking nodes as visited is important in BFS when finding connected components.

Consider what happens if you visit the same node multiple times.

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