Bipartite Graph Check in DSA Typescript - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

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

DSA Typescript

const color: number[] = new Array(graph.length).fill([1]);

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

A-1

B0

C1

Dnull

Attempts:

3 left

💡 Hint

Common Mistakes

Using 0 or 1 which are valid colors instead of -1.

Using null which is not a number.

We use -1 to mark all vertices as uncolored initially.

2fill in blank

medium

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

DSA Typescript

color[start] = [1];

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

A1

B0

C-1

D2

Attempts:

3 left

💡 Hint

Common Mistakes

Assigning -1 which means uncolored.

Assigning 1 which is the other color but not the start.

We start coloring the first vertex with color 0.

3fill in blank

hard

Fix the error in the condition to check if the neighbor has the same color as the current vertex.

DSA Typescript

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

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

Acurrent

Bneighbor

Cstart

Dgraph

Attempts:

3 left

💡 Hint

Common Mistakes

Comparing neighbor color with itself.

Using an unrelated variable like 'start' or 'graph'.

We compare the neighbor's color with the current vertex's color to detect conflict.

4fill in blank

hard

Fill both blanks to assign the opposite color to the neighbor and add it to the queue.

DSA Typescript

color[neighbor] = 1 - color[[1]];
queue.push([2]);

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

Acurrent

Bneighbor

Cstart

Dgraph

Attempts:

3 left

💡 Hint

Common Mistakes

Using 'neighbor' instead of 'current' for color assignment.

Pushing 'current' instead of 'neighbor' to the queue.

We assign the opposite color of the current vertex to the neighbor and add the neighbor to the queue for BFS.

5fill in blank

hard

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

DSA Typescript

while (queue.length > 0) {
  const [1] = queue.shift()!;
  for (const [2] of graph[[3]]) {
    if (color[neighbor] === -1) {
      color[neighbor] = 1 - color[current];
      queue.push(neighbor);
    } else if (color[neighbor] === color[current]) {
      return false;
    }
  }
}

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

Acurrent

Bneighbor

Dstart

Attempts:

3 left

💡 Hint

Common Mistakes

Using inconsistent variable names causing confusion.

Using 'start' instead of 'current' in the loop.

We dequeue 'current', iterate over its neighbors, and check colors to verify bipartite property.