Bipartite Graph Check in DSA Go - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Bipartite Check on Simple Graph

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

DSA Go

package main
import "fmt"

func isBipartite(graph [][]int) bool {
    n := len(graph)
    colors := make([]int, n)
    for i := range colors {
        colors[i] = -1
    }
    var dfs func(int, int) bool
    dfs = func(node, color int) bool {
        colors[node] = color
        for _, nei := range graph[node] {
            if colors[nei] == -1 {
                if !dfs(nei, 1-color) {
                    return false
                }
            } else if colors[nei] == color {
                return false
            }
        }
        return true
    }
    for i := 0; i < n; i++ {
        if colors[i] == -1 {
            if !dfs(i, 0) {
                return false
            }
        }
    }
    return true
}

func main() {
    graph := [][]int{{1,3},{0,2},{1,3},{0,2}}
    fmt.Println(isBipartite(graph))
}

A Compilation error

B false

C Runtime panic

D true

💡 Hint

Think about the graph edges and if nodes can be colored in two groups without conflict.

The graph is a square cycle (0-1-2-3-0), which is bipartite. The code colors nodes alternatingly and finds no conflicts, so it returns true.

❓ Predict Output

intermediate

Output of Bipartite Check on Non-Bipartite Graph

What is the output of this Go code checking bipartite on a triangle graph?

DSA Go

package main
import "fmt"

func isBipartite(graph [][]int) bool {
    n := len(graph)
    colors := make([]int, n)
    for i := range colors {
        colors[i] = -1
    }
    var dfs func(int, int) bool
    dfs = func(node, color int) bool {
        colors[node] = color
        for _, nei := range graph[node] {
            if colors[nei] == -1 {
                if !dfs(nei, 1-color) {
                    return false
                }
            } else if colors[nei] == color {
                return false
            }
        }
        return true
    }
    for i := 0; i < n; i++ {
        if colors[i] == -1 {
            if !dfs(i, 0) {
                return false
            }
        }
    }
    return true
}

func main() {
    graph := [][]int{{1,2},{0,2},{0,1}}
    fmt.Println(isBipartite(graph))
}

A Runtime panic

B false

C Compilation error

D true

💡 Hint

A triangle graph cannot be split into two groups without edges inside a group.

The triangle graph has an odd cycle, so it is not bipartite. The code detects a conflict and returns false.

🔧 Debug

advanced

Identify the Error in Bipartite Check Implementation

What error will this Go code produce when run?

DSA Go

package main
import "fmt"

func isBipartite(graph [][]int) bool {
    n := len(graph)
    colors := make([]int, n)
    for i := range colors {
        colors[i] = -1
    }
    var dfs func(int, int) bool
    dfs = func(node, color int) bool {
        colors[node] = color
        for _, nei := range graph[node] {
            if colors[nei] == -1 {
                if !dfs(nei, 1-color) {
                    return false
                }
            } else if colors[nei] == color {
                return false
            }
        }
        return true
    }
    for i := 0; i <= n; i++ {
        if colors[i] == -1 {
            if !dfs(i, 0) {
                return false
            }
        }
    }
    return true
}

func main() {
    graph := [][]int{{1},{0}}
    fmt.Println(isBipartite(graph))
}

A Index out of range runtime panic

B Compilation error due to invalid syntax

C Returns false

D Returns true

💡 Hint

Check the loop boundary in the for loop iterating over nodes.

The loop uses i <= n which causes an index out of range panic because valid indices are 0 to n-1.

🧠 Conceptual

advanced

Which Graph Property Guarantees Bipartiteness?

Which property of a graph guarantees that it is bipartite?

A The graph contains only even length cycles

B The graph contains no cycles

C The graph contains only odd length cycles

D The graph is complete

💡 Hint

Think about cycle lengths and coloring nodes in two groups.

A graph is bipartite if and only if it contains no odd length cycles. Even length cycles are allowed.

🚀 Application

expert

Resulting Color Groups After Bipartite Check

After running the bipartite check on this graph, what are the colors assigned to nodes? (0 or 1) Graph adjacency list: [[1,4],[0,2],[1,3],[2,4],[0,3]] Assume the algorithm colors node 0 with 0 first.

DSA Go

package main
import "fmt"

func isBipartiteColors(graph [][]int) ([]int, bool) {
    n := len(graph)
    colors := make([]int, n)
    for i := range colors {
        colors[i] = -1
    }
    var dfs func(int, int) bool
    dfs = func(node, color int) bool {
        colors[node] = color
        for _, nei := range graph[node] {
            if colors[nei] == -1 {
                if !dfs(nei, 1-color) {
                    return false
                }
            } else if colors[nei] == color {
                return false
            }
        }
        return true
    }
    for i := 0; i < n; i++ {
        if colors[i] == -1 {
            if !dfs(i, 0) {
                return nil, false
            }
        }
    }
    return colors, true
}

func main() {
    graph := [][]int{{1,4},{0,2},{1,3},{2,4},{0,3}}
    colors, ok := isBipartiteColors(graph)
    if ok {
        fmt.Println(colors)
    } else {
        fmt.Println("Not bipartite")
    }
}

A [0,1,1,0,1]

B [0,1,0,1,1]

C [0,1,0,1,0]

D [0,0,1,0,1]

💡 Hint

Trace the DFS coloring starting from node 0 with color 0.

Starting at node 0 with color 0, neighbors 1 and 4 get color 1, then 1's neighbor 2 gets 0, 2's neighbor 3 gets 1, and 4's neighbor 3 is already colored 1, no conflict.

Practice

1. What does it mean for a graph to be bipartite?

easy

A. It has an equal number of vertices and edges

B. All vertices have the same degree

C. It contains at least one cycle

D. Its vertices can be divided into two sets with no edges inside the same set

Solution

1. Step 1: Understand bipartite graph definition

   A bipartite graph is one where vertices can be split into two groups so that no edge connects vertices within the same group.

2. Step 2: Compare options with definition

   Its vertices can be divided into two sets with no edges inside the same set matches this definition exactly, while others describe unrelated properties.

3. Final Answer:

   Its vertices can be divided into two sets with no edges inside the same set -> Option D

4. Quick Check:

   Bipartite graph = Two sets, no internal edges [OK]

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

Common Mistakes:

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

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

easy

A. map[int][]int

B. []int

C. map[int]int

D. [][]int

Solution

1. Step 1: Identify graph representation needs

   We need to store each vertex and its connected vertices (neighbors).

2. Step 2: Match data structures to graph representation

   map[int][]int maps each vertex to a list of neighbors, perfect for adjacency list representation.

3. Final Answer:

   map[int][]int -> Option A

4. Quick Check:

   Adjacency list = map[int][]int [OK]

Hint: Use map[int][]int for adjacency list in Go [OK]

Common Mistakes:

• Using []int which is just a list, not graph
• Using map[int]int which maps to single int, not neighbors
• Using [][]int without clear vertex indexing

3. What will be the output of this Go code snippet checking bipartite for graph with edges: 0-1, 1-2, 2-3, 3-0?

graph := map[int][]int{
  0: {1, 3},
  1: {0, 2},
  2: {1, 3},
  3: {2, 0},
}
result := isBipartite(graph)
fmt.Println(result)

Assuming isBipartite returns true if graph is bipartite, false otherwise.

medium

A. false

B. Compilation error

C. true

D. Runtime panic

Solution

1. Step 1: Analyze the graph structure

   The graph forms a cycle of length 4: 0-1-2-3-0.

2. Step 2: Check bipartite condition for even cycle

   Even length cycles are bipartite, but here edges connect 0-3 and 2-3, making it a 4-cycle which is bipartite. However, 0-3 edge closes the cycle.

3. Step 3: Re-examine edges

   Edges are 0-1,1-2,2-3,3-0 forming a square (4-cycle). This is bipartite, so isBipartite should return true.

4. Final Answer:

   false -> Option A

5. Quick Check:

   Even cycle graph is bipartite = false [Incorrect]

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

Common Mistakes:

• Thinking all cycles are not bipartite
• Confusing edge directions
• Assuming runtime errors without code errors

4. Identify the bug in this Go function snippet for bipartite check:

func isBipartite(graph map[int][]int) bool {
  color := make(map[int]int)
  var dfs func(int, int) bool
  dfs = func(node, c int) bool {
    if val, ok := color[node]; ok {
      return val == c
    }
    color[node] = c
    for _, nei := range graph[node] {
      if !dfs(nei, 1-c) {
        return false
      }
    }
    return true
  }
  for node := range graph {
    if _, ok := color[node]; !ok {
      if !dfs(node, 0) {
        return false
      }
    }
  }
  return true
}

medium

A. Missing initialization of color map

B. Incorrect color flipping logic in dfs call

C. No bug, function correctly checks bipartite

D. DFS function does not return any value

Solution

1. Step 1: Review color map initialization

   color map is initialized properly with make(map[int]int).

2. Step 2: Check DFS logic and color flipping

   DFS flips color with 1-c correctly and returns false if conflict found.

3. Step 3: Confirm DFS returns and main loop

   DFS returns bool, main loop calls DFS on uncolored nodes, returns false if conflict.

4. Final Answer:

   No bug, function correctly checks bipartite -> Option C

5. Quick Check:

   DFS with color flipping and map works correctly [OK]

Hint: Check color flip and return values in DFS [OK]

Common Mistakes:

• Forgetting to flip color with 1-c
• Not returning DFS results properly
• Not initializing color map

5. Given a graph with vertices 0 to 5 and edges: 0-1, 1-2, 2-3, 3-4, 4-5, 5-0, 1-4. Is this graph bipartite?

hard

A. No, because it has disconnected components

B. Yes, because it has no odd cycles

C. Yes, because all vertices can be colored the same

D. No, because it contains an odd cycle

Solution

1. Step 1: Analyze the graph structure

   The graph is a cycle 0-1-2-3-4-5-0 of length 6 (even) with an additional edge 1-4.

2. Step 2: Check for odd-length cycles

   Check cycles involving the extra edge 1-4: cycle 1-4-5-0-1 has length 4 (even), but cycle 1-2-3-4-1 is length 4 (even). However, the presence of edge 1-4 creates a triangle 1-4-5-0-1? Actually, no triangle. But check carefully: 1-4-5-0-1 is length 4, no odd cycle. But 1-4-5-0-1 is 4 edges, so even. So no odd cycle. So graph is bipartite.

3. Final Answer:

   Yes, because it has no odd cycles -> Option B

4. Quick Check:

   No odd cycles = bipartite [OK]

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

Common Mistakes:

• Thinking the extra edge 1-4 creates an odd cycle
• Assuming all cycles are even without checking
• Confusing disconnected with bipartite