Bipartite Graph Check in DSA C++

Mental Model

A bipartite graph can be split into two groups where no edges connect nodes within the same group. We check this by trying to color nodes with two colors without conflicts.

Analogy: Imagine a party where guests are split into two rooms so that no two friends are in the same room. If you can seat everyone this way, the party plan is bipartite.

Group A: 1 -> 3 -> 5
Group B: 2 -> 4 -> 6
Edges only go between groups, never inside one.

Example graph:
1 -> 2
|    |
3 -> 4

No edges connect nodes in the same group.

Dry Run Walkthrough

Input: Graph with edges: 1-2, 2-3, 3-4, 4-1 (square cycle)

Goal: Check if the graph is bipartite by coloring nodes with two colors without conflicts

Step 1: Start coloring node 1 with color 0

Colors: [1:0, 2:-1, 3:-1, 4:-1]

Why: We pick a starting node and assign the first color

Step 2: Color neighbors of 1: node 2 with color 1, node 4 with color 1

Colors: [1:0, 2:1, 3:-1, 4:1]

Why: Neighbors must have opposite color to avoid same-group edges

Step 3: Color neighbor of 2: node 3 with color 0

Colors: [1:0, 2:1, 3:0, 4:1]

Why: Neighbor of node 2 must have opposite color to node 2

Step 4: Check neighbors of 3 and 4 for conflicts; none found

Colors unchanged: [1:0, 2:1, 3:0, 4:1]

Why: No adjacent nodes share the same color, so no conflict

Result:

Colors: 1(0) -> 2(1) -> 3(0) -> 4(1) -> null
Graph is bipartite

Annotated Code

DSA C++

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

class Graph {
public:
    int V;
    vector<vector<int>> adj;

    Graph(int V) {
        this->V = V;
        adj.resize(V + 1);
    }

    void addEdge(int u, int v) {
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    bool isBipartite() {
        vector<int> color(V + 1, -1);
        for (int start = 1; start <= V; start++) {
            if (color[start] == -1) {
                queue<int> q;
                q.push(start);
                color[start] = 0; // assign first color

                while (!q.empty()) {
                    int u = q.front();
                    q.pop();

                    for (int v : adj[u]) {
                        if (color[v] == -1) {
                            color[v] = 1 - color[u]; // opposite color
                            q.push(v);
                        } else if (color[v] == color[u]) {
                            return false; // same color neighbor found
                        }
                    }
                }
            }
        }
        return true;
    }
};

int main() {
    Graph g(4);
    g.addEdge(1, 2);
    g.addEdge(2, 3);
    g.addEdge(3, 4);
    g.addEdge(4, 1);

    if (g.isBipartite()) {
        cout << "Graph is bipartite\n";
    } else {
        cout << "Graph is NOT bipartite\n";
    }
    return 0;
}

color[start] = 0; // assign first color

assign initial color to start node to begin bipartite check

for (int v : adj[u]) {

iterate over neighbors of current node u

if (color[v] == -1) {

if neighbor not colored, assign opposite color and enqueue

color[v] = 1 - color[u]; // opposite color

assign opposite color to neighbor to maintain bipartite property

else if (color[v] == color[u]) {

if neighbor has same color, graph is not bipartite

return false; // same color neighbor found

stop and report graph is not bipartite due to conflict

Output

Graph is bipartite

Complexity Analysis

Time: O(V + E) because we visit each vertex and edge once during BFS

Space: O(V) for the color array and BFS queue

vs Alternative: Compared to DFS, BFS is equally efficient here; naive methods checking all partitions would be exponential

Edge Cases

Empty graph (no edges)

Returns true since no edges mean no conflicts

DSA C++

if (color[start] == -1) {

Graph with single node

Returns true as single node can be colored any color

DSA C++

color[start] = 0; // assign first color

Graph with odd cycle (e.g., triangle 1-2-3-1)

Returns false because odd cycle cannot be bipartite

DSA C++

else if (color[v] == color[u]) {

When to Use This Pattern

When you need to split graph nodes into two groups with no edges inside groups, use bipartite check with two-color BFS or DFS to detect conflicts.

Common Mistakes

Mistake: Not checking all connected components, missing disconnected parts
Fix: Loop over all nodes and run BFS/DFS if uncolored to cover disconnected components

Mistake: Assigning same color to neighbors instead of opposite
Fix: Assign neighbor color as 1 - current node color to ensure opposite coloring

Summary

Checks if a graph can be divided into two groups with no edges inside the same group.

Use when you need to verify if a graph is bipartite, especially in problems involving two-coloring or grouping.

The key insight is to color nodes with two colors using BFS/DFS and detect any coloring conflicts.

Practice

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

easy

A. It contains at least one cycle of odd length

B. It has an equal number of vertices and edges

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

D. All vertices have the same degree

Solution

1. Step 1: Understand bipartite graph definition

   A bipartite graph means vertices can be split into two sets where no edge connects vertices within the same set.

2. Step 2: Compare options with definition

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

3. Final Answer:

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

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 graphs must have cycles
• Assuming all vertices have same degree

2. Which of the following C++ code snippets correctly initializes a graph as an adjacency list for bipartite check?

easy

A. vector graph(n);

B. vector<int> graph(n);

C. int graph[n][n];

D. map graph;

Solution

1. Step 1: Identify adjacency list structure

   An adjacency list for a graph with n vertices is best represented as vector of vectors: vector graph(n);

2. Step 2: Check other options

   vector<int> graph(n); is a vector of ints, not suitable for adjacency lists. int graph[n][n]; is a 2D array but less flexible. map graph; is a map of int to int, not adjacency list.

3. Final Answer:

   vector graph(n); -> Option A

4. Quick Check:

   Adjacency list = vector of vectors [OK]

Hint: Use vector of vectors for adjacency list in C++ [OK]

Common Mistakes:

• Using vector<int> instead of vector
• Using fixed size arrays limiting flexibility
• Using map which is not adjacency list

3. What is the output of the following code snippet that checks if a graph is bipartite?

int n = 4;
vector graph = {{1,3}, {0,2}, {1,3}, {0,2}};
vector<int> color(n, -1);

function dfs = [&](int node, int c) {
    color[node] = c;
    for (int neigh : graph[node]) {
        if (color[neigh] == -1) {
            if (!dfs(neigh, 1 - c)) return false;
        } else if (color[neigh] == c) {
            return false;
        }
    }
    return true;
};

bool result = true;
for (int i = 0; i < n; i++) {
    if (color[i] == -1) {
        if (!dfs(i, 0)) {
            result = false;
            break;
        }
    }
}
cout << (result ? "YES" : "NO") << endl;

medium

A. Runtime Error

B. NO

C. Compilation Error

D. YES

Solution

1. Step 1: Analyze graph structure

   The graph edges connect vertices 0-1, 0-3, 1-2, 2-3 forming a square (even cycle), which is bipartite.

2. Step 2: Trace DFS coloring

   DFS colors nodes alternatingly. No adjacent nodes share the same color, so dfs returns true for all nodes.

3. Final Answer:

   YES -> Option D

4. Quick Check:

   Even cycle graph is bipartite = YES [OK]

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

Common Mistakes:

• Assuming all cycles are non-bipartite
• Confusing color assignment logic
• Ignoring disconnected components

4. Identify the bug in this bipartite check code snippet:

bool dfs(int node, int c, vector& graph, vector<int>& color) {
    color[node] = c;
    for (int neigh : graph[node]) {
        if (color[neigh] == -1) {
            dfs(neigh, 1 - c, graph, color);
        } else if (color[neigh] == c) {
            return false;
        }
    }
    return true;
}

medium

A. Missing return value check for recursive dfs call

B. Wrong color assignment to nodes

C. Using vector<int> instead of vector<bool>

D. Incorrect graph representation

Solution

1. Step 1: Check recursive call handling

   The recursive dfs call result is not checked. If it returns false, the function should also return false immediately.

2. Step 2: Explain fix

   Adding 'if (!dfs(...)) return false;' ensures early exit on conflict detection.

3. Final Answer:

   Missing return value check for recursive dfs call -> Option A

4. Quick Check:

   Always check recursive call results in DFS [OK]

Hint: Return false immediately if recursive DFS fails [OK]

Common Mistakes:

• Ignoring recursive call return values
• Assigning wrong colors
• Using wrong data structures for graph

5. Given a graph with 5 vertices and edges: (0-1), (1-2), (2-3), (3-4), (4-1), which statement is true about its bipartite property?

hard

A. The graph is bipartite because it has no odd cycles

B. The graph is not bipartite because it contains an odd cycle

C. The graph is bipartite because all vertices have degree 2

D. The graph is not bipartite because it is disconnected

Solution

1. Step 1: Identify cycles in the graph

   The edges form a cycle: 1-2-3-4-1 which has 4 edges (even length). However, the full cycle including vertices 0-1-4-3-2-1 forms a cycle of length 5 (odd cycle): 0-1-4-3-2-1 (0-1,1-4,4-3,3-2,2-1).

2. Step 2: Check bipartite condition

   Since the graph contains an odd cycle of length 5, it is not bipartite.

3. Step 3: Re-examine options

   The graph is bipartite because it has no odd cycles is false. The graph is not bipartite because it contains an odd cycle is true. The graph is bipartite because all vertices have degree 2 is incorrect reasoning. The graph is not bipartite because it is disconnected is false because the graph is connected.

4. Final Answer:

   The graph is not bipartite because it contains an odd cycle -> Option B

5. Quick Check:

   Odd cycle means not bipartite [OK]

Hint: Check cycle lengths: odd cycle means not bipartite [OK]

Common Mistakes:

• Miscounting cycle length
• Confusing connectivity with bipartite property
• Assuming degree affects bipartite