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.