Connected Components Using BFS in DSA C# - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of BFS Connected Components Count

What is the output of the following C# code that counts connected components using BFS?

DSA C#

using System;
using System.Collections.Generic;

class Program {
    static int CountConnectedComponents(int n, List<int>[] graph) {
        bool[] visited = new bool[n];
        int count = 0;
        for (int i = 0; i < n; i++) {
            if (!visited[i]) {
                count++;
                Queue<int> queue = new Queue<int>();
                queue.Enqueue(i);
                visited[i] = true;
                while (queue.Count > 0) {
                    int node = queue.Dequeue();
                    foreach (int neighbor in graph[node]) {
                        if (!visited[neighbor]) {
                            visited[neighbor] = true;
                            queue.Enqueue(neighbor);
                        }
                    }
                }
            }
        }
        return count;
    }

    static void Main() {
        int n = 5;
        List<int>[] graph = new List<int>[n];
        for (int i = 0; i < n; i++) graph[i] = new List<int>();
        graph[0].Add(1);
        graph[1].Add(0);
        graph[2].Add(3);
        graph[3].Add(2);
        // Node 4 is isolated
        Console.WriteLine(CountConnectedComponents(n, graph));
    }
}

A 4

B 2

C 1

D 3

💡 Hint

Count how many groups of nodes are connected directly or indirectly.

The graph has three connected components: {0,1}, {2,3}, and {4} isolated. So the count is 3.

🧠 Conceptual

intermediate

Understanding BFS for Connected Components

Why does BFS help in finding connected components in an undirected graph?

A Because BFS sorts nodes in ascending order to find components.

B Because BFS explores all nodes reachable from a starting node, marking them visited, thus identifying one connected component at a time.

C Because BFS only visits nodes with even indices.

D Because BFS deletes edges after visiting nodes.

💡 Hint

Think about how BFS visits nodes layer by layer.

BFS starts from a node and visits all nodes reachable from it, marking them visited. This set of nodes forms one connected component. Repeating BFS from unvisited nodes finds other components.

❓ Predict Output

advanced

Output of BFS Connected Components with Cycle

What is the output of the following C# code counting connected components using BFS on a graph with a cycle?

DSA C#

using System;
using System.Collections.Generic;

class Program {
    static int CountConnectedComponents(int n, List<int>[] graph) {
        bool[] visited = new bool[n];
        int count = 0;
        for (int i = 0; i < n; i++) {
            if (!visited[i]) {
                count++;
                Queue<int> queue = new Queue<int>();
                queue.Enqueue(i);
                visited[i] = true;
                while (queue.Count > 0) {
                    int node = queue.Dequeue();
                    foreach (int neighbor in graph[node]) {
                        if (!visited[neighbor]) {
                            visited[neighbor] = true;
                            queue.Enqueue(neighbor);
                        }
                    }
                }
            }
        }
        return count;
    }

    static void Main() {
        int n = 6;
        List<int>[] graph = new List<int>[n];
        for (int i = 0; i < n; i++) graph[i] = new List<int>();
        graph[0].Add(1);
        graph[1].Add(0);
        graph[1].Add(2);
        graph[2].Add(1);
        graph[2].Add(3);
        graph[3].Add(2);
        graph[3].Add(0);
        graph[0].Add(3);
        graph[4].Add(5);
        graph[5].Add(4);
        Console.WriteLine(CountConnectedComponents(n, graph));
    }
}

A 2

B 3

C 1

D 4

💡 Hint

Count groups of nodes connected directly or indirectly, cycles do not increase count.

Nodes 0,1,2,3 form one connected component with a cycle. Nodes 4 and 5 form another. So total 2 components.

🔧 Debug

advanced

Identify the Bug in BFS Connected Components Code

What error will the following C# code produce when counting connected components using BFS?

DSA C#

using System;
using System.Collections.Generic;

class Program {
    static int CountConnectedComponents(int n, List<int>[] graph) {
        bool[] visited = new bool[n];
        int count = 0;
        for (int i = 0; i <= n; i++) { // Note the <= instead of <
            if (!visited[i]) {
                count++;
                Queue<int> queue = new Queue<int>();
                queue.Enqueue(i);
                visited[i] = true;
                while (queue.Count > 0) {
                    int node = queue.Dequeue();
                    foreach (int neighbor in graph[node]) {
                        if (!visited[neighbor]) {
                            visited[neighbor] = true;
                            queue.Enqueue(neighbor);
                        }
                    }
                }
            }
        }
        return count;
    }

    static void Main() {
        int n = 3;
        List<int>[] graph = new List<int>[n];
        for (int i = 0; i < n; i++) graph[i] = new List<int>();
        graph[0].Add(1);
        graph[1].Add(0);
        graph[1].Add(2);
        graph[2].Add(1);
        Console.WriteLine(CountConnectedComponents(n, graph));
    }

A StackOverflowException

B NullReferenceException

C IndexOutOfRangeException

D No error, output is 1

💡 Hint

Check the loop boundary condition for array access.

The for loop uses i <= n which tries to access visited[n], out of bounds causing IndexOutOfRangeException.

🚀 Application

expert

Number of Connected Components After Edge Removal

Given a graph with 7 nodes and edges: (0-1), (1-2), (2-3), (3-0), (4-5), (5-6), (6-4), if the edge (1-2) is removed, what is the number of connected components?

A 2

B 3

C 4

D 1

💡 Hint

In a cycle, removing one edge does not disconnect the graph; it becomes a path.

The graph originally has two connected components: {0,1,2,3} and {4,5,6}. Removing edge (1-2) does not disconnect the first component because there is still a path 1-0-3-2. Thus, still 2 components.

Practice

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

easy

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

B. The shortest path between two nodes

C. The node with the highest degree

D. The total number of edges in the graph

Solution

1. Step 1: Understand BFS in context of connected components

   BFS explores all nodes reachable from a given start node, marking them as part of the same connected component.

2. Step 2: Identify what BFS finds in this use case

   It finds all nodes connected directly or indirectly to the start node, grouping them as one connected component.

3. Final Answer:

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

4. Quick Check:

   BFS finds connected nodes = D [OK]

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

Common Mistakes:

• Confusing BFS with shortest path only
• Thinking BFS counts edges instead of nodes
• Assuming BFS finds node degrees

2. Which of the following is the correct way to declare a queue for BFS in C#?

easy

A. Dictionary queue = new Dictionary();

B. List<int> queue = new List<int>();

C. Stack<int> queue = new Stack<int>();

D. Queue<int> queue = new Queue<int>();

Solution

1. Step 1: Identify the data structure for BFS queue

   BFS requires a queue to process nodes in FIFO order, so Queue<T> is used in C#.

2. Step 2: Check syntax correctness

   Queue<int> queue = new Queue<int>(); correctly declares an empty queue of integers.

3. Final Answer:

   Queue<int> queue = new Queue<int>(); -> Option D

4. Quick Check:

   Queue declaration for BFS = A [OK]

Hint: Use Queue<T> for BFS traversal in C# [OK]

Common Mistakes:

• Using List instead of Queue for BFS
• Using Stack which is LIFO, not FIFO
• Confusing Dictionary with queue

3. Given the following graph adjacency list and BFS code snippet, what is the output list of connected components?

var graph = new Dictionary {
  {1, new List<int>{2}},
  {2, new List<int>{1, 3}},
  {3, new List<int>{2}},
  {4, new List<int>{5}},
  {5, new List<int>{4}}
};

List connectedComponents = new List();
HashSet<int> visited = new HashSet<int>();

foreach (var node in graph.Keys) {
  if (!visited.Contains(node)) {
    Queue<int> queue = new Queue<int>();
    List<int> component = new List<int>();
    queue.Enqueue(node);
    visited.Add(node);
    while (queue.Count > 0) {
      int current = queue.Dequeue();
      component.Add(current);
      foreach (var neighbor in graph[current]) {
        if (!visited.Contains(neighbor)) {
          visited.Add(neighbor);
          queue.Enqueue(neighbor);
        }
      }
    }
    connectedComponents.Add(component);
  }
}

foreach (var comp in connectedComponents) {
  Console.WriteLine(string.Join(",", comp));
}

medium

A. "1,2,3\n4,5"

B. "1,3,2\n4,5"

C. "1,2\n3,4,5"

D. "1,2,3,4,5"

Solution

1. Step 1: Trace BFS from node 1

   Starting at 1, BFS visits 1, then 2, then 3. Component is [1,2,3].

2. Step 2: Trace BFS from node 4

   Next unvisited node is 4, BFS visits 4 and 5. Component is [4,5].

3. Final Answer:

   "1,2,3\n4,5" -> Option A

4. Quick Check:

   Connected components = [1,2,3] and [4,5] [OK]

Hint: BFS groups connected nodes in order visited [OK]

Common Mistakes:

• Mixing order of nodes in components
• Assuming all nodes are in one component
• Forgetting to mark visited nodes

4. Identify the bug in the following BFS code for connected components:

foreach (var node in graph.Keys) {
  if (!visited.Contains(node)) {
    Queue<int> queue = new Queue<int>();
    List<int> component = new List<int>();
    queue.Enqueue(node);
    // Missing visited.Add(node);
    while (queue.Count > 0) {
      int current = queue.Dequeue();
      component.Add(current);
      foreach (var neighbor in graph[current]) {
        if (!visited.Contains(neighbor)) {
          visited.Add(neighbor);
          queue.Enqueue(neighbor);
        }
      }
    }
    connectedComponents.Add(component);
  }
}

medium

A. Neighbors are not added to the queue

B. The starting node is not marked visited before BFS loop

C. The queue is not initialized

D. The component list is not cleared

Solution

1. Step 1: Check visited marking for start node

   The code does not mark the starting node as visited before BFS, so it may be processed multiple times.

2. Step 2: Understand BFS consequences

   Without marking start node visited, BFS can enqueue it repeatedly causing infinite loop or wrong components.

3. Final Answer:

   The starting node is not marked visited before BFS loop -> Option B

4. Quick Check:

   Start node must be visited first [OK]

Hint: Always mark start node visited before BFS loop [OK]

Common Mistakes:

• Forgetting to mark start node visited
• Marking visited after enqueueing neighbors only
• Not initializing queue properly

5. You have a graph with nodes 1 to 7 and edges: (1-2), (2-3), (4-5), (5-6), (6-4), (7). Using BFS to find connected components, how many components will be found and which nodes belong to the largest component?

hard

A. 3 components; largest component nodes: [4,5,6,7]

B. 2 components; largest component nodes: [1,2,3,4,5,6]

C. 3 components; largest component nodes: [4,5,6]

D. 4 components; largest component nodes: [1,2,3]

Solution

1. Step 1: Identify connected components from edges

   Edges form three groups: (1,2,3), (4,5,6), and isolated node (7). So 3 components total.

2. Step 2: Determine largest component

   Components (1,2,3) and (4,5,6) both have 3 nodes; largest size is 3. 3 components; largest component nodes: [4,5,6] correctly lists [4,5,6].

3. Final Answer:

   3 components; largest component nodes: [4,5,6] -> Option C

4. Quick Check:

   3 components, largest = [4,5,6] [OK]

Hint: Count isolated groups; largest has most nodes [OK]

Common Mistakes:

• Counting isolated node as connected
• Merging separate components incorrectly
• Miscounting number of components