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.

Practice

1. What does it mean if a graph is bipartite?

easy

A. Its vertices can be divided into two groups with no edges inside the same group

B. It has an equal number of vertices and edges

C. It contains at least one cycle

D. All vertices have the same degree

Solution

1. Step 1: Understand bipartite graph definition

   A bipartite graph can be split into two sets where no edges connect vertices within the same set.

2. Step 2: Compare options with definition

   Only Its vertices can be divided into two groups with no edges inside the same group matches this definition exactly.

3. Final Answer:

   Its vertices can be divided into two groups with no edges inside the same group -> Option A

4. Quick Check:

   Bipartite = Two groups, no internal edges [OK]

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

Common Mistakes:

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

2. Which TypeScript data structure is best to represent a graph for bipartite check?

easy

A. Adjacency list using Map

B. Array of numbers

C. String array

D. Single number variable

Solution

1. Step 1: Identify graph representation needs

   We need to store edges for each vertex efficiently to check bipartite property.

2. Step 2: Choose suitable data structure

   An adjacency list using Map stores neighbors for each vertex clearly and is efficient.

3. Final Answer:

   Adjacency list using Map<number, number[]> -> Option A

4. Quick Check:

   Graph as adjacency list = Map [OK]

Hint: Use adjacency list (Map) for graph edges [OK]

Common Mistakes:

• Using simple arrays without edge info
• Using strings which don't represent graph
• Using single variable instead of structure

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

const graph = new Map([
  [0, [1, 3]],
  [1, [0, 2]],
  [2, [1, 3]],
  [3, [0, 2]]
]);

function isBipartite(graph: Map): boolean {
  const color = new Map();
  for (const node of graph.keys()) {
    if (!color.has(node)) {
      const queue = [node];
      color.set(node, 0);
      while (queue.length) {
        const u = queue.shift()!;
        for (const v of graph.get(u)!) {
          if (!color.has(v)) {
            color.set(v, 1 - color.get(u)!);
            queue.push(v);
          } else if (color.get(v) === color.get(u)) {
            return false;
          }
        }
      }
    }
  }
  return true;
}

console.log(isBipartite(graph));

medium

A. false

B. true

C. undefined

D. SyntaxError

Solution

1. Step 1: Analyze graph structure

   The graph is a square cycle: 0-1-2-3-0, which is an even cycle and bipartite.

2. Step 2: Trace BFS coloring

   Starting from node 0 with color 0, neighbors get color 1, their neighbors color 0, no conflicts found.

3. Final Answer:

   true -> Option B

4. Quick Check:

   Even cycle graph is bipartite = true [OK]

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

Common Mistakes:

• Assuming all cycles are not bipartite
• Confusing color assignment logic
• Missing BFS queue processing

4. Find the bug in this TypeScript function that checks if a graph is bipartite:

function isBipartite(graph: Map): boolean {
  const color = new Map();
  for (const node of graph.keys()) {
    if (!color.has(node)) {
      const queue = [node];
      color.set(node, 0);
      while (queue.length) {
        const u = queue.shift()!;
        for (const v of graph.get(u)!) {
          if (!color.has(v)) {
            color.set(v, color.get(u)!);
            queue.push(v);
          } else if (color.get(v) === color.get(u)) {
            return false;
          }
        }
      }
    }
  }
  return true;
}

medium

A. Missing return type boolean

B. queue.shift()! should be queue.pop()

C. color.set(v, color.get(u)!) should be color.set(v, 1 - color.get(u)!)

D. graph.get(u)! should be graph.get(v)!

Solution

1. Step 1: Identify color assignment error

   The code assigns the same color to neighbors, which breaks bipartite logic.

2. Step 2: Correct color assignment

   Neighbors must get opposite color: 1 - color of current node.

3. Final Answer:

   color.set(v, 1 - color.get(u)!) -> Option C

4. Quick Check:

   Neighbor color = opposite of current [OK]

Hint: Neighbors must have opposite colors [OK]

Common Mistakes:

• Assigning same color to neighbors
• Using pop instead of shift in BFS
• Incorrect graph access

5. Given a graph represented as adjacency list:

const graph = new Map([
  [0, [1, 2]],
  [1, [0, 3]],
  [2, [0, 3]],
  [3, [1, 2, 4]],
  [4, [3]]
]);

Is this graph bipartite? Choose the correct reasoning.

hard

A. Yes, because it has no odd-length cycles

B. No, because node 3 connects to nodes in the same set

C. Yes, because all nodes have even degree

D. No, because it contains a triangle (3-cycle)

Solution

1. Step 1: Identify cycles in the graph

   There is a triangle cycle: nodes 1-3-2-1 (edges 1-3, 3-2, 2-1), which is an odd-length cycle.

2. Step 2: Recall bipartite property about cycles

   Graphs containing odd-length cycles are not bipartite.

3. Final Answer:

   No, because it contains a triangle (3-cycle) -> Option D

4. Quick Check:

   Odd cycle present = not bipartite [OK]

Hint: Odd cycles mean graph is not bipartite [OK]

Common Mistakes:

• Falsely identifying triangle in 1-2-3 (actually 1-3-2 forms triangle)
• Assuming even degree means bipartite
• Confusing connectivity with bipartite property