Bipartite Graph Check in DSA C - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to initialize the color array with -1 for all vertices.

DSA C

for (int i = 0; i < V; i++) {
    color[i] = [1];
}

Drag options to blanks, or click blank then click option'

A-1

B0

C1

Di

Attempts:

3 left

💡 Hint

Common Mistakes

Using 0 or 1 instead of -1 for uncolored vertices.

Using the loop variable i as color.

We initialize all vertices with color -1 to indicate they are uncolored initially.

2fill in blank

medium

Complete the code to assign the first color (0) to the starting vertex in BFS.

DSA C

color[start] = [1];

Drag options to blanks, or click blank then click option'

A0

B-1

Cstart

D1

Attempts:

3 left

💡 Hint

Common Mistakes

Assigning -1 which means uncolored.

Assigning 1 instead of 0.

We assign color 0 to the starting vertex to begin the bipartite coloring.

3fill in blank

hard

Fix the error in the condition to check if adjacent vertex has the same color.

DSA C

if (color[v] == color[[1]]) {
    return false;
}

Drag options to blanks, or click blank then click option'

Astart

Bv

Cu

Di

Attempts:

3 left

💡 Hint

Common Mistakes

Comparing color[v] with color[v] (always true).

Using wrong variable like start or i.

We compare the color of adjacent vertex v with the current vertex u to detect conflict.

4fill in blank

hard

Fill both blanks to assign the opposite color to adjacent vertex and push it to the queue.

DSA C

color[v] = [1] - color[u];
queue[rear++] = [2];

Drag options to blanks, or click blank then click option'

A1

Bu

Cv

D0

Attempts:

3 left

💡 Hint

Common Mistakes

Assigning same color instead of opposite.

Pushing wrong vertex to queue.

We assign the opposite color by subtracting from 1 and enqueue the adjacent vertex v.

5fill in blank

hard

Fill all three blanks to complete the BFS loop for bipartite check.

DSA C

while (front != rear) {
    int u = queue[[1]++];
    for (int i = 0; i < adj[u].size; i++) {
        int v = adj[u].array[[2]];
        if (color[v] == -1) {
            color[v] = [3] - color[u];
            queue[rear++] = v;
        } else if (color[v] == color[u]) {
            return false;
        }
    }
}

Drag options to blanks, or click blank then click option'

Afront

Bi

C1

Drear

Attempts:

3 left

💡 Hint

Common Mistakes

Using rear instead of front for dequeue.

Using wrong index for adjacency array.

Assigning wrong color value.

We dequeue from front, iterate over neighbors using i, and assign opposite color 1 - color[u].