Bipartite Graph Check in DSA C# - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Bipartite Check on a Simple Graph

What is the output of the following C# code that checks if the given graph is bipartite?

DSA C#

using System;
using System.Collections.Generic;

class Program {
    static bool IsBipartite(List<int>[] graph) {
        int n = graph.Length;
        int[] colors = new int[n];
        for (int i = 0; i < n; i++) colors[i] = -1;

        for (int i = 0; i < n; i++) {
            if (colors[i] == -1) {
                Queue<int> queue = new Queue<int>();
                queue.Enqueue(i);
                colors[i] = 0;

                while (queue.Count > 0) {
                    int node = queue.Dequeue();
                    foreach (int neighbor in graph[node]) {
                        if (colors[neighbor] == -1) {
                            colors[neighbor] = 1 - colors[node];
                            queue.Enqueue(neighbor);
                        } else if (colors[neighbor] == colors[node]) {
                            return false;
                        }
                    }
                }
            }
        }
        return true;
    }

    static void Main() {
        List<int>[] graph = new List<int>[4];
        for (int i = 0; i < 4; 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);

        Console.WriteLine(IsBipartite(graph));
    }
}

A Compilation error

B True

C False

D Runtime exception

💡 Hint

Think about whether the graph can be colored using two colors without adjacent nodes sharing the same color.

The graph is a simple chain 0-1-2-3 which can be colored alternately with two colors, so it is bipartite.

❓ Predict Output

intermediate

Output of Bipartite Check on a Triangle Graph

What is the output of the following C# code that checks if the given graph is bipartite?

DSA C#

using System;
using System.Collections.Generic;

class Program {
    static bool IsBipartite(List<int>[] graph) {
        int n = graph.Length;
        int[] colors = new int[n];
        for (int i = 0; i < n; i++) colors[i] = -1;

        for (int i = 0; i < n; i++) {
            if (colors[i] == -1) {
                Queue<int> queue = new Queue<int>();
                queue.Enqueue(i);
                colors[i] = 0;

                while (queue.Count > 0) {
                    int node = queue.Dequeue();
                    foreach (int neighbor in graph[node]) {
                        if (colors[neighbor] == -1) {
                            colors[neighbor] = 1 - colors[node];
                            queue.Enqueue(neighbor);
                        } else if (colors[neighbor] == colors[node]) {
                            return false;
                        }
                    }
                }
            }
        }
        return true;
    }

    static void Main() {
        List<int>[] graph = new List<int>[3];
        for (int i = 0; i < 3; 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(0);
        graph[0].Add(2);

        Console.WriteLine(IsBipartite(graph));
    }
}

A Compilation error

B True

C False

D Runtime exception

💡 Hint

A triangle graph has an odd cycle. Think if it can be bipartite.

A triangle (3-node cycle) cannot be bipartite because it has an odd cycle, so the function returns false.

🔧 Debug

advanced

Identify the Bug in Bipartite Check Code

The following code is intended to check if a graph is bipartite. It sometimes returns incorrect results. What is the bug?

DSA C#

using System;
using System.Collections.Generic;

class Program {
    static bool IsBipartite(List<int>[] graph) {
        int n = graph.Length;
        int[] colors = new int[n];
        for (int i = 0; i < n; i++) colors[i] = 0;

        for (int i = 0; i < n; i++) {
            if (colors[i] == 0) {
                Queue<int> queue = new Queue<int>();
                queue.Enqueue(i);
                colors[i] = 1;

                while (queue.Count > 0) {
                    int node = queue.Dequeue();
                    foreach (int neighbor in graph[node]) {
                        if (colors[neighbor] == 0) {
                            colors[neighbor] = 3 - colors[node];
                            queue.Enqueue(neighbor);
                        } else if (colors[neighbor] == colors[node]) {
                            return false;
                        }
                    }
                }
            }
        }
        return true;
    }
}

A Colors array is initialized with 0, which conflicts with color 0 used in logic; should initialize with -1.

B Queue is not cleared between BFS runs, causing incorrect traversal.

C The graph adjacency list is not checked for null before iteration.

D The colors are assigned as 1 and 3, which are invalid color values.

💡 Hint

Check how the colors array is initialized and used in the code.

The code uses 0 to mean uncolored, but initializes colors with 0, so it treats all nodes as colored initially, skipping BFS.

🧠 Conceptual

advanced

Properties of Bipartite Graphs

Which of the following statements is TRUE about bipartite graphs?

A A graph is bipartite if and only if it contains no odd-length cycles.

B All bipartite graphs are trees.

C Bipartite graphs always have an equal number of vertices in both sets.

D A bipartite graph cannot contain any cycles.

💡 Hint

Think about the relationship between cycles and bipartite property.

A graph is bipartite if and only if it has no odd-length cycles. Even cycles are allowed.

🚀 Application

expert

Determine the Number of Connected Components That Are Bipartite

Given the following graph represented as adjacency lists, how many connected components are bipartite?

DSA C#

using System;
using System.Collections.Generic;

class Program {
    static bool IsBipartiteComponent(List<int>[] graph, int start, int[] colors) {
        Queue<int> queue = new Queue<int>();
        queue.Enqueue(start);
        colors[start] = 0;

        while (queue.Count > 0) {
            int node = queue.Dequeue();
            foreach (int neighbor in graph[node]) {
                if (colors[neighbor] == -1) {
                    colors[neighbor] = 1 - colors[node];
                    queue.Enqueue(neighbor);
                } else if (colors[neighbor] == colors[node]) {
                    return false;
                }
            }
        }
        return true;
    }

    static void Main() {
        int n = 7;
        List<int>[] graph = new List<int>[n];
        for (int i = 0; i < n; i++) graph[i] = new List<int>();

        // Component 1: 0-1-2 (chain)
        graph[0].Add(1);
        graph[1].Add(0);
        graph[1].Add(2);
        graph[2].Add(1);

        // Component 2: 3-4-5-3 (triangle with extra node)
        graph[3].Add(4);
        graph[4].Add(3);
        graph[4].Add(5);
        graph[5].Add(4);
        graph[5].Add(3);
        graph[3].Add(5);

        // Component 3: 6 (isolated node)

        int[] colors = new int[n];
        for (int i = 0; i < n; i++) colors[i] = -1;

        int bipartiteCount = 0;
        for (int i = 0; i < n; i++) {
            if (colors[i] == -1) {
                if (IsBipartiteComponent(graph, i, colors)) {
                    bipartiteCount++;
                }
            }
        }

        Console.WriteLine(bipartiteCount);
    }
}

A 0

B 3

C 1

D 2

💡 Hint

Check each connected component for bipartite property separately.

Component 1 is bipartite (chain), component 2 contains a triangle (odd cycle) so not bipartite, component 3 is a single node (bipartite). So total 2 bipartite components.

Practice

1. What does it mean for a graph to be bipartite?

easy

A. All vertices have the same degree

B. It has an equal number of vertices and edges

C. It contains at least one cycle

D. Its vertices can be divided into two groups with no edges inside the same group

Solution

1. Step 1: Understand bipartite graph definition

   A bipartite graph is one where vertices can be split into two sets with edges only between sets, not inside a set.

2. Step 2: Compare options with definition

   Its vertices can be divided into two groups with no edges inside the same group matches this definition exactly, while others describe unrelated properties.

3. Final Answer:

   Its vertices can be divided into two groups with no edges inside the same group -> Option D

4. Quick Check:

   Bipartite graph = two groups, no internal edges [OK]

Hint: Bipartite means two groups with no edges inside groups [OK]

Common Mistakes:

• Confusing bipartite with equal vertices and edges
• Thinking bipartite means no cycles
• Assuming all vertices have same degree

2. Which C# data structure is best to represent a graph for bipartite check?

easy

A. List adjacency list

B. Dictionary adjacency list

C. int[,] adjacency matrix

D. HashSet<int> for vertices only

Solution

1. Step 1: Identify graph representation needs

   We need to store edges efficiently and access neighbors quickly for bipartite check.

2. Step 2: Evaluate options

   Dictionary allows flexible vertex keys and fast neighbor lookup, better than fixed-size arrays or sets.

3. Final Answer:

   Dictionary adjacency list -> Option B

4. Quick Check:

   Dictionary adjacency list = best for flexible graphs [OK]

Hint: Use Dictionary for flexible graph edges [OK]

Common Mistakes:

• Using HashSet only stores vertices, no edges
• Adjacency matrix wastes space for sparse graphs
• List lacks vertex key mapping

3. What is the output of this C# code snippet checking bipartite for a graph with edges: 0-1, 1-2, 2-3, 3-0?

var graph = new Dictionary {
  {0, new List<int>{1,3}},
  {1, new List<int>{0,2}},
  {2, new List<int>{1,3}},
  {3, new List<int>{2,0}}
};
bool IsBipartite(Dictionary g) {
  var color = new Dictionary();
  foreach(var node in g.Keys) {
    if(!color.ContainsKey(node)) {
      var queue = new Queue<int>();
      queue.Enqueue(node);
      color[node] = 0;
      while(queue.Count > 0) {
        var u = queue.Dequeue();
        foreach(var v in g[u]) {
          if(!color.ContainsKey(v)) {
            color[v] = 1 - color[u];
            queue.Enqueue(v);
          } else if(color[v] == color[u]) {
            return false;
          }
        }
      }
    }
  }
  return true;
}
Console.WriteLine(IsBipartite(graph));

medium

A. True

B. False

C. Compilation error

D. Runtime exception

Solution

1. Step 1: Analyze the graph structure

   The graph forms a cycle of length 4: 0-1-2-3-0.

2. Step 2: Check bipartite condition on even cycle

   Even cycles are bipartite, but here the cycle is length 4 (even), so it should be bipartite. However, the code returns false if adjacent nodes have same color.

3. Step 3: Trace coloring

   Coloring alternates 0 and 1 around the cycle, no conflict occurs, so function returns true.

4. Final Answer:

   True -> Option A

5. Quick Check:

   Even cycle graph is bipartite = True [OK]

Hint: Even cycles are bipartite; odd cycles are not [OK]

Common Mistakes:

• Assuming all cycles are not bipartite
• Confusing color assignment logic
• Ignoring queue BFS traversal

4. Identify the bug in this bipartite check code snippet:

bool CheckBipartite(Dictionary graph) {
  var color = new Dictionary();
  foreach(var node in graph.Keys) {
    if(!color.ContainsKey(node)) {
      color[node] = 0;
      var stack = new Stack<int>();
      stack.Push(node);
      while(stack.Count > 0) {
        var u = stack.Pop();
        foreach(var v in graph[u]) {
          if(!color.ContainsKey(v)) {
            color[v] = color[u];
            stack.Push(v);
          } else if(color[v] == color[u]) {
            return false;
          }
        }
      }
    }
  }
  return true;
}

medium

A. Colors assigned to neighbors are same as current node, should be opposite

B. Stack should be replaced with queue for BFS

C. Missing initialization of color dictionary

D. No return statement for true case

Solution

1. Step 1: Review color assignment logic

   Neighbors must have opposite colors to current node for bipartite check.

2. Step 2: Identify incorrect assignment

   Code assigns neighbor color same as current node, causing false negatives.

3. Final Answer:

   Colors assigned to neighbors are same as current node, should be opposite -> Option A

4. Quick Check:

   Neighbor colors must differ [OK]

Hint: Neighbors must have opposite colors, not same [OK]

Common Mistakes:

• Assigning same color to neighbors
• Confusing stack vs queue (both work but BFS preferred)
• Forgetting to initialize colors

5. Given a graph with vertices 0 to 5 and edges: 0-1, 1-2, 2-3, 3-4, 4-5, 5-0, and 1-4, is the graph bipartite? Explain why.

hard

A. Yes, because all cycles are even length

B. No, because it has a self-loop

C. No, because it contains an odd cycle including edges 1-2-3-4-1

D. Yes, because it has no cycles

Solution

1. Step 1: Identify cycles in the graph

   The graph has a large cycle 0-1-2-3-4-5-0 (length 6, even), and with edge 1-4, cycles 1-2-3-4-1 (length 4, even) and 0-1-4-5-0 (length 4, even).

2. Step 2: Check for odd-length cycles

   No odd-length cycles exist. A graph is bipartite if and only if it has no odd-length cycles.

3. Final Answer:

   No, because it contains an odd cycle including edges 1-2-3-4-1 -> Option C

4. Quick Check:

   Odd cycle means not bipartite [OK]

Hint: Check for odd cycles to decide bipartite [OK]

Common Mistakes:

• Miscounting cycle lengths
• Assuming any cycle means not bipartite
• Ignoring extra edges creating odd cycles