Bipartite Graph Check in DSA Typescript - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Bipartite Check on Simple Graph

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

DSA Typescript

function isBipartite(graph: number[][]): boolean {
  const n = graph.length;
  const colors = new Array(n).fill(-1);

  for (let i = 0; i < n; i++) {
    if (colors[i] === -1) {
      const queue: number[] = [i];
      colors[i] = 0;

      while (queue.length) {
        const node = queue.shift()!;
        for (const neighbor of graph[node]) {
          if (colors[neighbor] === -1) {
            colors[neighbor] = 1 - colors[node];
            queue.push(neighbor);
          } else if (colors[neighbor] === colors[node]) {
            return false;
          }
        }
      }
    }
  }
  return true;
}

const graph = [[1,3],[0,2],[1,3],[0,2]];
console.log(isBipartite(graph));

A SyntaxError

B false

C TypeError

D true

💡 Hint

Think about whether the graph can be colored with two colors without conflicts.

The graph is a square cycle (0-1-2-3-0). It can be colored with two colors alternating, so it is bipartite.

❓ Predict Output

intermediate

Output of Bipartite Check on Non-Bipartite Graph

What is the output of this TypeScript code that checks if a graph is bipartite?

DSA Typescript

function isBipartite(graph: number[][]): boolean {
  const n = graph.length;
  const colors = new Array(n).fill(-1);

  for (let i = 0; i < n; i++) {
    if (colors[i] === -1) {
      const queue: number[] = [i];
      colors[i] = 0;

      while (queue.length) {
        const node = queue.shift()!;
        for (const neighbor of graph[node]) {
          if (colors[neighbor] === -1) {
            colors[neighbor] = 1 - colors[node];
            queue.push(neighbor);
          } else if (colors[neighbor] === colors[node]) {
            return false;
          }
        }
      }
    }
  }
  return true;
}

const graph = [[1,2],[0,2],[0,1]];
console.log(isBipartite(graph));

A RangeError

B false

C ReferenceError

D true

💡 Hint

Check if the graph contains an odd cycle.

The graph is a triangle (0-1-2-0), which is an odd cycle and not bipartite.

🧠 Conceptual

advanced

Why BFS is used in Bipartite Check?

Why is Breadth-First Search (BFS) commonly used to check if a graph is bipartite?

A Because BFS finds shortest paths which are needed to detect cycles.

B Because BFS uses less memory than DFS in all cases.

C Because BFS colors nodes level by level, ensuring neighbors get opposite colors.

D Because BFS can only be used on bipartite graphs.

💡 Hint

Think about how BFS explores nodes in layers.

BFS explores nodes level by level, so it assigns colors alternately to neighbors, which helps detect conflicts in bipartite coloring.

🔧 Debug

advanced

Identify the Bug in Bipartite Check Code

What error will this TypeScript code produce when checking if a graph is bipartite?

DSA Typescript

function isBipartite(graph: number[][]): boolean {
  const n = graph.length;
  const colors = new Array(n).fill(-1);

  for (let i = 0; i < n; i++) {
    if (colors[i] === -1) {
      const queue: number[] = [i];
      colors[i] = 0;

      while (queue.length) {
        const node = queue.pop()!;
        for (const neighbor of graph[node]) {
          if (colors[neighbor] === -1) {
            colors[neighbor] = 1 - colors[node];
            queue.push(neighbor);
          } else if (colors[neighbor] === colors[node]) {
            return false;
          }
        }
      }
    }
  }
  return true;
}

const graph = [[1,3],[0,2],[1,3],[0,2]];
console.log(isBipartite(graph));

A The code returns false incorrectly due to using stack behavior instead of queue.

B The code throws a TypeError because of wrong array method.

C The code returns true correctly.

D The code causes an infinite loop.

💡 Hint

Check how nodes are removed from the queue.

Using pop() makes the queue behave like a stack (DFS), which can cause incorrect coloring order and false negatives.

🚀 Application

expert

Number of Connected Components in Bipartite Graph

Given a graph represented as adjacency lists, how many connected components does the following graph have? Also, is it bipartite?

DSA Typescript

const graph = [
  [1],    // Node 0 connected to 1
  [0],    // Node 1 connected to 0
  [3],    // Node 2 connected to 3
  [2],    // Node 3 connected to 2
  []      // Node 4 isolated
];

A 3 connected components, graph is bipartite

B 2 connected components, graph is bipartite

C 3 connected components, graph is not bipartite

D 2 connected components, graph is not bipartite

💡 Hint

Count isolated nodes and check if each component can be colored with two colors.

The graph has three connected components: {0,1}, {2,3}, and {4} isolated. Each component is bipartite because they are simple edges or isolated nodes.