Bipartite Graph Check in DSA C - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Bipartite Check on Simple Graph

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

DSA C

#include <stdio.h>
#include <stdbool.h>
#define V 4

int graph[V][V] = {
    {0, 1, 0, 1},
    {1, 0, 1, 0},
    {0, 1, 0, 1},
    {1, 0, 1, 0}
};

bool isBipartiteUtil(int v, int colorArr[], int c) {
    colorArr[v] = c;
    for (int i = 0; i < V; i++) {
        if (graph[v][i]) {
            if (colorArr[i] == -1) {
                if (!isBipartiteUtil(i, colorArr, 1 - c))
                    return false;
            } else if (colorArr[i] == c) {
                return false;
            }
        }
    }
    return true;
}

bool isBipartite() {
    int colorArr[V];
    for (int i = 0; i < V; i++)
        colorArr[i] = -1;

    for (int i = 0; i < V; i++) {
        if (colorArr[i] == -1) {
            if (!isBipartiteUtil(i, colorArr, 0))
                return false;
        }
    }
    return true;
}

int main() {
    if (isBipartite())
        printf("Graph is Bipartite\n");
    else
        printf("Graph is NOT Bipartite\n");
    return 0;
}

A Compilation error

B Graph is NOT Bipartite

C Runtime error

D Graph is Bipartite

💡 Hint

Check if the graph can be colored using two colors without adjacent nodes sharing the same color.

The given graph is a square cycle (4 nodes connected in a cycle). Such even-length cycles are bipartite. The code colors nodes alternately and finds no conflict, so it prints 'Graph is Bipartite'.

❓ Predict Output

intermediate

Output of Bipartite Check on Odd Cycle Graph

What is the output of this C code checking bipartiteness on a triangle graph?

DSA C

#include <stdio.h>
#include <stdbool.h>
#define V 3

int graph[V][V] = {
    {0, 1, 1},
    {1, 0, 1},
    {1, 1, 0}
};

bool isBipartiteUtil(int v, int colorArr[], int c) {
    colorArr[v] = c;
    for (int i = 0; i < V; i++) {
        if (graph[v][i]) {
            if (colorArr[i] == -1) {
                if (!isBipartiteUtil(i, colorArr, 1 - c))
                    return false;
            } else if (colorArr[i] == c) {
                return false;
            }
        }
    }
    return true;
}

bool isBipartite() {
    int colorArr[V];
    for (int i = 0; i < V; i++)
        colorArr[i] = -1;

    for (int i = 0; i < V; i++) {
        if (colorArr[i] == -1) {
            if (!isBipartiteUtil(i, colorArr, 0))
                return false;
        }
    }
    return true;
}

int main() {
    if (isBipartite())
        printf("Graph is Bipartite\n");
    else
        printf("Graph is NOT Bipartite\n");
    return 0;
}

A Graph is Bipartite

B Graph is NOT Bipartite

C Compilation error

D Segmentation fault

💡 Hint

Odd cycles cannot be bipartite.

The graph is a triangle (3 nodes all connected). Odd cycles are not bipartite because you cannot color nodes with two colors without adjacent nodes sharing the same color.

🔧 Debug

advanced

Identify the bug causing incorrect bipartite detection

This code is intended to check if a graph is bipartite. What is the bug causing it to always return true, even for non-bipartite graphs?

DSA C

#include <stdio.h>
#include <stdbool.h>
#define V 3

int graph[V][V] = {
    {0, 1, 1},
    {1, 0, 1},
    {1, 1, 0}
};

bool isBipartiteUtil(int v, int colorArr[], int c) {
    colorArr[v] = c;
    for (int i = 0; i < V; i++) {
        if (graph[v][i]) {
            if (colorArr[i] == -1) {
                if (!isBipartiteUtil(i, colorArr, 1 - c))
                    return false;
            } else if (colorArr[i] == c) {
                return false;
            }
        }
    }
    return true;
}

bool isBipartite() {
    int colorArr[V];
    for (int i = 0; i < V; i++)
        colorArr[i] = -1;

    for (int i = 0; i < V; i++) {
        if (colorArr[i] == -1) {
            if (!isBipartiteUtil(i, colorArr, 0))
                return false;
        }
    }
    return true;
}

int main() {
    if (isBipartite())
        printf("Graph is Bipartite\n");
    else
        printf("Graph is NOT Bipartite\n");
    return 0;
}

A Graph adjacency matrix is incorrect

B Incorrect initialization of colorArr array

C Missing return statement in recursive call of isBipartiteUtil

D Wrong base case in isBipartiteUtil

💡 Hint

Check if the recursive call's return value is used properly.

The recursive call to isBipartiteUtil does not return its result. So even if a false is found deeper, it is ignored and the function returns true.

🧠 Conceptual

advanced

Which graph property guarantees bipartiteness?

Which of the following properties guarantees that a graph is bipartite?

A Graph contains no odd-length cycles

B Graph is complete

C Graph is connected

D Graph has an Eulerian path

💡 Hint

Think about cycles and coloring.

A graph is bipartite if and only if it contains no odd-length cycles. Other properties do not guarantee bipartiteness.

🚀 Application

expert

Result of Bipartite Check on Disconnected Graph

Consider a graph with two disconnected components: one is a triangle (3 nodes all connected), the other is a line of two nodes connected. What will the bipartite check output be?

A Graph is NOT Bipartite

B Runtime error due to disconnected graph

C Depends on starting node

D Graph is Bipartite

💡 Hint

Check bipartiteness on all components.

The graph is disconnected but bipartite check runs on all components. The triangle component is not bipartite, so overall graph is not bipartite.

Practice

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

easy

A. It contains at least one cycle

B. Its vertices can be divided into two sets with no edges inside the same set

C. It has an equal number of vertices and edges

D. All vertices have the same degree

Solution

1. Step 1: Understand bipartite graph definition

   A bipartite graph is one where vertices can be split into two groups so that no edge connects vertices within the same group.

2. Step 2: Compare options with definition

   Only Its vertices can be divided into two sets with no edges inside the same set matches this definition exactly. Other options describe unrelated properties.

3. Final Answer:

   Its vertices can be divided into two sets with no edges inside the same set -> Option B

4. Quick Check:

   Bipartite graph = two sets, no same-set edges [OK]

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

Common Mistakes:

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

2. Which of the following C code snippets correctly initializes a graph adjacency list for bipartite check?

easy

A. int graph[5][5] = {{0}};

B. int graph[5]; for(int i=0; i<5; i++) graph[i] = NULL;

C. int graph[][] = {0};

D. int* graph[5]; for(int i=0; i<5; i++) graph[i] = malloc(sizeof(int)*5); memset(graph[i], 0, sizeof(int)*5);

Solution

1. Step 1: Understand adjacency list initialization in C

   Adjacency list uses array of pointers to arrays or linked lists. int* graph[5]; for(int i=0; i<5; i++) graph[i] = malloc(sizeof(int)*5); memset(graph[i], 0, sizeof(int)*5); correctly allocates memory and initializes it.

2. Step 2: Check other options for correctness

   int graph[5][5] = {{0}}; is a fixed 2D array but only zero-initialized; B tries to assign NULL to int array elements (invalid); C has incomplete array declaration.

3. Final Answer:

   int* graph[5]; for(int i=0; i<5; i++) graph[i] = malloc(sizeof(int)*5); memset(graph[i], 0, sizeof(int)*5); -> Option D

4. Quick Check:

   Proper adjacency list init = malloc + memset [OK]

Hint: Use malloc and memset to init adjacency lists in C [OK]

Common Mistakes:

• Trying to assign NULL to int array elements
• Using incomplete array declarations
• Not allocating memory for adjacency lists

3. Given the following graph edges: 0-1, 1-2, 2-3, 3-0, what will the bipartite check function return?

medium

A. Runtime error due to cycle

B. false (graph is not bipartite)

C. true (graph is bipartite)

D. Indeterminate result

Solution

1. Step 1: Analyze the graph structure

   The edges form a cycle of length 4: 0-1-2-3-0. Even length cycles can be bipartite, so this graph is bipartite.

2. Step 2: Check bipartite condition on cycle

   Since the cycle length is even, the graph can be colored with two colors without conflict.

3. Final Answer:

   true (graph is bipartite) -> Option C

4. Quick Check:

   Even cycle = bipartite [OK]

Hint: Even length cycles are bipartite, odd length are not [OK]

Common Mistakes:

• Assuming all cycles are not bipartite
• Confusing cycle length parity
• Thinking runtime error occurs due to cycles

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

bool isBipartite(int graph[][3], int V) {
  int color[V];
  for(int i=0; i

medium

A. Function does not check disconnected components

B. Color array is not initialized to -1

C. Queue is not initialized properly

D. Incorrect color assignment logic

Solution

1. Step 1: Understand the code logic

   The code colors nodes starting from node 0 and uses BFS to assign colors to neighbors.

2. Step 2: Identify missing checks

   The code only starts BFS from node 0 and does not check other disconnected components, which may cause incorrect results if graph is disconnected.

3. Step 3: Verify other options

   Queue is properly initialized; color array is initialized to -1; color assignment logic is correct.

4. Final Answer:

   Function does not check disconnected components -> Option A

5. Quick Check:

   Check all components for bipartite [OK]

Hint: Always check all graph components in bipartite check [OK]

Common Mistakes:

• Ignoring disconnected graph parts
• Assuming single BFS covers entire graph
• Misunderstanding color assignment

5. You have a graph with 6 vertices and edges: 0-1, 0-3, 1-2, 2-3, 4-5. Which statement is true about its bipartite nature?

hard

A. The graph is bipartite because all components are bipartite

B. The graph is not bipartite because of the cycle 0-1-2-3-0

C. The graph is bipartite only if vertex 4 is connected to vertex 2

D. The graph is not bipartite because vertices 4 and 5 form an odd cycle

Solution

1. Step 1: Analyze graph components

   Vertices 0-1-2-3 form a cycle 0-1-2-3-0 of length 4 (even), which is bipartite. Vertices 4-5 form a separate edge, also bipartite.

2. Step 2: Check bipartite condition for entire graph

   Since all components are bipartite, the entire graph is bipartite.

3. Step 3: Evaluate other options

   The graph is not bipartite because of the cycle 0-1-2-3-0 is wrong because even cycles are bipartite. The graph is bipartite only if vertex 4 is connected to vertex 2 is irrelevant. The graph is not bipartite because vertices 4 and 5 form an odd cycle is wrong because 4-5 is just an edge, no cycle.

4. Final Answer:

   The graph is bipartite because all components are bipartite -> Option A

5. Quick Check:

   All components bipartite = graph bipartite [OK]

Hint: Check each component's bipartite status separately [OK]

Common Mistakes:

• Assuming any cycle means not bipartite
• Ignoring disconnected components
• Confusing edges with cycles