Bipartite graph

Intuition:

A bipartite graph is a graph that can be colored using 2 colors such that no adjacent nodes have the same color. Any linear graph with no cycle is always a bipartite graph. With a cycle, any graph with an even cycle length can also be a bipartite graph. So, any graph with an odd cycle length can never be a bipartite graph.

To check if the graph is bipartite, it can check if the nodes can be colored alternatingly. If alternate coloring of nodes is possible, the graph is bipartite, else not.

Approach:

Initialize a color array with all nodes initially uncolored represented by -1. Green and Yellow colors will be represented as integer value 0 and 1 respectively.
Start the BFS traversal from an unvisited node and perform the following steps:
- If a node is uncolored, color it with alternating colors.
- If a node is previously colored, check if it follows alternate colors. If not, the graph can be said as not bipartite.
If all the nodes can be colored with alternating colors, the graph can be classified as bipartite.

Dry Run:

Solution:

#include <bits/stdc++.h>
using namespace std;

class Solution {
private:
    
    /* Function to perform BFS traversal and color
    the nodes with alternate colors in a component */
    bool bfs(int start, int V, vector<int> adj[], int color[]) {
        // Queue for BFS traversal
        queue <int> q;
        
        // Add initial node to queue
        q.push(start);
        color[start] = 0; // Mark it with a color
        
        // While queue is not empty
        while(!q.empty()) {
            // Get the node
            int node = q.front();
            q.pop();
            
            // Traverse all its neighbors
            for(auto it : adj[node]) {
                
                // If not already colored
                if(color[it] == -1) {
                    
                    // Color it with opposite color.
                    color[it] = !color[node];
                    
                    // Push the node in queue
                    q.push(it);
                }
                
                // Else if the neighbor has same color as node
                else if(color[it] == color[node]) {
                    
                    /* Return false, as the 
                    component is not bipartite */
                    return false;
                }
            }
        }
        
        // Return true is the component is bipartite
        return true;
    }
    
    
public:
    /* Function to check if the 
    given graph is bipartite */
    bool isBipartite(int V, vector<int> adj[]) {
        
        /* To store the color of nodes, where 
        each node is uncolored initially */
        int color[V];
        for(int i=0; i < V; i++) color[i] = -1;
        
        // Traverse all the nodes 
        for(int i=0; i < V; i++) {
            
            // If not colored, start the traversal
            if(color[i] == -1) {
                // Return false if graph is not bipartite
                if(!bfs(i, V, adj, color))
                    return false;
            }
        }
        
        /* Return true if each 
        component is bipartite */
        return true;
    }
};

int main() {
    
    int V = 4;
    vector<int> adj[V] = {
        {1,3},
        {0,2},
        {1,3},
        {0,2}
    };
    
    /* Creating an instance of 
    Solution class */
    Solution sol; 
    
    /* Function call to check 
    if the given graph is bipartite */
    bool ans = sol.isBipartite(V, adj);
    
    // Output
    if(ans) 
        cout << "The given graph is a bipartite graph.";
    else 
        cout << "The given graph is not a bipartite graph.";
    
    return 0;
}
import java.util.*;

class Solution {

    /* Function to perform BFS traversal and color
    the nodes with alternate colors in a component */
    private boolean bfs(int start, int V, List<Integer>[] adj, 
                        int[] color) {
        // Queue for BFS traversal
        Queue<Integer> q = new LinkedList<>();
        
        // Add initial node to queue
        q.add(start);
        color[start] = 0; // Mark it with a color
        
        // While queue is not empty
        while (!q.isEmpty()) {
            // Get the node
            int node = q.poll();
            
            // Traverse all its neighbors
            for (int it : adj[node]) {
                
                // If not already colored
                if (color[it] == -1) {
                    
                    // Color it with opposite color.
                    color[it] = 1 - color[node];
                    
                    // Push the node in queue
                    q.add(it);
                }
                
                // Else if the neighbor has same color as node
                else if (color[it] == color[node]) {
                    
                    /* Return false, as the 
                    component is not bipartite */
                    return false;
                }
            }
        }
        
        // Return true if the component is bipartite
        return true;
    }

    /* Function to check if the 
    given graph is bipartite */
    public boolean isBipartite(int V, List<Integer>[] adj) {
        
        /* To store the color of nodes, where 
        each node is uncolored initially */
        int[] color = new int[V];
        Arrays.fill(color, -1);
        
        // Traverse all the nodes 
        for (int i = 0; i < V; i++) {
            
            // If not colored, start the traversal
            if (color[i] == -1) {
                // Return false if graph is not bipartite
                if (!bfs(i, V, adj, color))
                    return false;
            }
        }
        
        /* Return true if each 
        component is bipartite */
        return true;
    }

    public static void main(String[] args) {
        int V = 4;
        List<Integer>[] adj = new List[V];
        for (int i = 0; i < V; i++) {
            adj[i] = new ArrayList<>();
        }
        adj[0].addAll(Arrays.asList(1, 3));
        adj[1].addAll(Arrays.asList(0, 2));
        adj[2].addAll(Arrays.asList(1, 3));
        adj[3].addAll(Arrays.asList(0, 2));

        /* Creating an instance of 
        Solution class */
        Solution sol = new Solution(); 
        
        /* Function call to check 
        if the given graph is bipartite */
        boolean ans = sol.isBipartite(V, adj);
        
        // Output
        if (ans) 
            System.out.println("The given graph is a bipartite graph.");
        else 
            System.out.println("The given graph is not a bipartite graph.");
    }
}
from collections import deque

class Solution:
    
    # Function to perform BFS traversal and color
    # the nodes with alternate colors in a component
    def bfs(self, start, V, adj, color):
        # Queue for BFS traversal
        q = deque()
        
        # Add initial node to queue
        q.append(start)
        color[start] = 0 # Mark it with a color
        
        # While queue is not empty
        while q:
            # Get the node
            node = q.popleft()
            
            # Traverse all its neighbors
            for it in adj[node]:
                
                # If not already colored
                if color[it] == -1:
                    
                    # Color it with opposite color.
                    color[it] = 1 - color[node]
                    
                    # Push the node in queue
                    q.append(it)
                
                # Else if the neighbor has same color as node
                elif color[it] == color[node]:
                    
                    # Return false, as the 
                    # component is not bipartite
                    return False
        
        # Return true if the component is bipartite
        return True
    
    # Function to check if the 
    # given graph is bipartite
    def isBipartite(self, V, adj):
        
        # To store the color of nodes, where 
        # each node is uncolored initially
        color = [-1] * V
        
        # Traverse all the nodes 
        for i in range(V):
            
            # If not colored, start the traversal
            if color[i] == -1:
                # Return false if graph is not bipartite
                if not self.bfs(i, V, adj, color):
                    return False
        
        # Return true if each 
        # component is bipartite
        return True

if __name__ == "__main__":
    
    V = 4
    adj = [
        [1, 3],
        [0, 2],
        [1, 3],
        [0, 2]
    ]
    
    # Creating an instance of 
    # Solution class
    sol = Solution()
    
    # Function call to check 
    # if the given graph is bipartite
    ans = sol.isBipartite(V, adj)
    
    # Output
    if ans:
        print("The given graph is a bipartite graph.")
    else:
        print("The given graph is not a bipartite graph.")
class Solution {
    
    /* Function to perform BFS traversal and color
    the nodes with alternate colors in a component */
    bfs(start, V, adj, color) {
        // Queue for BFS traversal
        const q = [];
        
        // Add initial node to queue
        q.push(start);
        color[start] = 0; // Mark it with a color
        
        // While queue is not empty
        while (q.length > 0) {
            // Get the node
            const node = q.shift();
            
            // Traverse all its neighbors
            for (const it of adj[node]) {
                
                // If not already colored
                if (color[it] === -1) {
                    
                    // Color it with opposite color.
                    color[it] = 1 - color[node];
                    
                    // Push the node in queue
                    q.push(it);
                }
                
                // Else if the neighbor has same color as node
                else if (color[it] === color[node]) {
                    
                    // Return false, as the 
                    // component is not bipartite
                    return false;
                }
            }
        }
        
        // Return true if the component is bipartite
        return true;
    }
    
    /* Function to check if the 
    given graph is bipartite */
    isBipartite(V, adj) {
        
        // To store the color of nodes, where 
        // each node is uncolored initially
        const color = Array(V).fill(-1);
        
        // Traverse all the nodes 
        for (let i = 0; i < V; i++) {
            
            // If not colored, start the traversal
            if (color[i] === -1) {
                // Return false if graph is not bipartite
                if (!this.bfs(i, V, adj, color))
                    return false;
            }
        }
        
        // Return true if each 
        // component is bipartite
        return true;
    }
}

Complexity Analysis:

Time Complexity: O(V+E) (where V is the number of nodes and E is the number of edges in the graph)
The BFS Traversal takes O(V+E) time.

Space Complexity: O(V)
The color array takes O(V) space and queue space for BFS is O(V) for the worst case.

Intuition:

A bipartite graph is a graph that can be colored using 2 colors such that no adjacent nodes have the same colour. Any linear graph with no cycle is always a bipartite graph. With a cycle, any graph with an even cycle length can also be a bipartite graph. So, any graph with an odd cycle length can never be a bipartite graph.

In order to check if the given graph is bipartite, it can checked if the nodes can be colors alternatingly. If alternate coloring of nodes is possible, the graph is bipartite, else not.

Approach:

Initialize a color array with all nodes initially uncolored represented by -1. Green and Yellow colors will be represented as integer value 0 and 1 respectively.
Start the DFS traversal from the node and perform the following steps:
- If a node is uncolored, color it with alternating colors.
- If a node is previously colored, check if it follows alternate colors. If not, the graph can be said as not bipartite.
If all the nodes can be colored with alternating colors, the graph can be classified as bipartite.

Dry Run:

Solution:

#include <bits/stdc++.h>
using namespace std;

class Solution {
private:

    /* Function to perform DFS traversal and 
    color the nodes with alternate colors*/
    bool dfs(int node, int col, vector<int> &color, 
             vector<int> adj[]) {
        
        // Color the current node
        color[node] = col; 
        
        // Traverse adjacent nodes
        for(auto it : adj[node]) {
            
            // if uncoloured
            if(color[it] == -1) {
                
                // Recursively color the nodes 
                if(dfs(it, !col, color, adj) == false) 
                    return false; 
            }
            
            // if previously coloured and have the same colour
            else if(color[it] == col) {
                
                // Return false as it is not bipartite
                return false; 
            }
        }
        
        /* Return true if all the nodes can 
        be colored with alternate colors */
        return true; 
    }

public:
    /* Function to check if the 
    given graph is bipartite */
    bool isBipartite(int V, vector<int> adj[]) {
        
        /* To store the color of nodes, where 
        each node is uncolored initially */
        vector<int> color(V, -1);
        
        // Start Traversal of connected components
        for(int i=0; i<V; i++) {
            
            /* if a node is not colored, 
            a new component is found */
            if(color[i] == -1) {
                
                /* Start DFS traversal 
                and color each node */
                if(dfs(i, 0, color, adj) == false) {
                    
                    /* Return false if component 
                    is found not to be bipartite */
                    return false;
                }
            }
        }
        
        /* Return true if each 
        component is bipartite */
        return true;
    }
};

int main() {
    
    int V = 4;
    vector<int> adj[V] = {
        {1,3},
        {0,2},
        {1,3},
        {0,2}
    };
    
    /* Creating an instance of 
    Solution class */
    Solution sol; 
    
    /* Function call to check 
    if the given graph is bipartite */
    bool ans = sol.isBipartite(V, adj);
    
    // Output
    if(ans) 
        cout << "The given graph is a bipartite graph.";
    else 
        cout << "The given graph is not a bipartite graph.";
    
    return 0;
}
import java.util.*;

class Solution {
    
    /* Function to perform DFS traversal and 
    color the nodes with alternate colors*/
    private boolean dfs(int node, int col, int[] color, 
                        List<Integer> adj[]) {
                            
        // Color the current node
        color[node] = col;

        // Traverse adjacent nodes
        for(int it : adj[node]) {
            
            // if uncoloured
            if(color[it] == -1) {
                
                // Recursively color the nodes 
                if(dfs(it, 1 - col, color, adj) == false) 
                    return false; 
            }
            
            // if previously coloured and have the same colour
            else if(color[it] == col) {
                
                // Return false as it is not bipartite
                return false; 
            }
        }
        
        // Return true if all the nodes can 
        // be colored with alternate colors
        return true; 
    }

    // Function to check if the given graph is bipartite
    public boolean isBipartite(int V, List<Integer> adj[]) {
        
        // To store the color of nodes, where 
        // each node is uncolored initially
        int[] color = new int[V];
        Arrays.fill(color, -1);

        // Start Traversal of connected components
        for(int i = 0; i < V; i++) {
            
            // if a node is not colored, 
            // a new component is found
            
            if(color[i] == -1) {
                // Start DFS traversal 
                // and color each node
                
                if(dfs(i, 0, color, adj) == false) {
                    
                    // Return false if component 
                    // is found not to be bipartite
                    return false;
                }
            }
        }
        
        // Return true if each 
        // component is bipartite
        return true;
    }
}

public class Main {
    public static void main(String[] args) {
        int V = 4;
        List<Integer> adj[] = new ArrayList[V];
        for (int i = 0; i < V; i++) {
            adj[i] = new ArrayList<>();
        }
        adj[0].add(1);
        adj[0].add(3);
        adj[1].add(0);
        adj[1].add(2);
        adj[2].add(1);
        adj[2].add(3);
        adj[3].add(0);
        adj[3].add(2);

        // Creating an instance of Solution class
        Solution sol = new Solution();

        // Function call to check if the given graph is bipartite
        boolean ans = sol.isBipartite(V, adj);

        // Output
        if(ans)
            System.out.println("The given graph is a bipartite graph.");
        else
            System.out.println("The given graph is not a bipartite graph.");
    }
}
class Solution:
    
    # Function to perform DFS traversal and 
    # color the nodes with alternate colors
    def dfs(self, node, col, color, adj):
        
        # Color the current node
        color[node] = col
        
        # Traverse adjacent nodes
        for it in adj[node]:
            
            # if uncoloured
            if color[it] == -1:
                
                # Recursively color the nodes 
                if not self.dfs(it, 1 - col, color, adj):
                    return False
                    
            # if previously coloured and have the same colour
            elif color[it] == col:
                
                # Return false as it is not bipartite
                return False
        
        # Return true if all the nodes can 
        # be colored with alternate colors
        return True

    # Function to check if the given graph is bipartite
    def isBipartite(self, V, adj):
        
        # To store the color of nodes, where 
        # each node is uncolored initially
        color = [-1] * V
        
        # Start Traversal of connected components
        for i in range(V):
            
            # if a node is not colored, 
            # a new component is found
            if color[i] == -1:
                
                # Start DFS traversal 
                # and color each node
                if not self.dfs(i, 0, color, adj):
                    
                    # Return false if component 
                    # is found not to be bipartite
                    return False
        
        # Return true if each 
        # component is bipartite
        return True

if __name__ == "__main__":
    V = 4
    adj = [[] for _ in range(V)]
    adj[0].extend([1, 3])
    adj[1].extend([0, 2])
    adj[2].extend([1, 3])
    adj[3].extend([0, 2])

    # Creating an instance of Solution class
    sol = Solution()

    # Function call to check if the given graph is bipartite
    ans = sol.isBipartite(V, adj)

    # Output
    if ans:
        print("The given graph is a bipartite graph.")
    else:
        print("The given graph is not a bipartite graph.")
class Solution {

    /* Function to perform DFS traversal and 
    color the nodes with alternate colors*/
    dfs(node, col, color, adj) {
        // Color the current node
        color[node] = col;

        // Traverse adjacent nodes
        for (let it of adj[node]) {
            // if uncoloured
            if (color[it] === -1) {
                // Recursively color the nodes 
                if (!this.dfs(it, 1 - col, color, adj)) 
                    return false;
            }
            // if previously coloured and have the same colour
            else if (color[it] === col) {
                // Return false as it is not bipartite
                return false;
            }
        }
        // Return true if all the nodes can 
        // be colored with alternate colors
        return true;
    }

    /* Function to check if the 
    given graph is bipartite */
    isBipartite(V, adj) {
        // To store the color of nodes, where 
        // each node is uncolored initially
        let color = new Array(V).fill(-1);

        // Start Traversal of connected components
        for (let i = 0; i < V; i++) {
            // if a node is not colored, 
            // a new component is found
            if (color[i] === -1) {
                // Start DFS traversal 
                // and color each node
                if (!this.dfs(i, 0, color, adj)) {
                    // Return false if component 
                    // is found not to be bipartite
                    return false;
                }
            }
        }
        // Return true if each 
        // component is bipartite
        return true;
    }
}

const main = () => {
    const V = 4;
    const adj = [
        [1, 3],
        [0, 2],
        [1, 3],
        [0, 2]
    ];

    // Creating an instance of Solution class
    const sol = new Solution();

    // Function call to check if the given graph is bipartite
    const ans = sol.isBipartite(V, adj);

    // Output
    if (ans) 
        console.log("The given graph is a bipartite graph.");
    else 
        console.log("The given graph is not a bipartite graph.");
}

main();

Complexity Analysis:

Time Complexity: O(V+E) (where V is the number of nodes and E is the number of edges in the graph.)
The DFS Traversal takes O(V+E) time.

Space Complexity: O(V)
The color array takes O(V) space and recursion stack space for DFS is O(V) for the worst case.

Problem List

Examples:

Constraints

Hints

Company Tags

Editorial

Intuition:

Approach:

Dry Run:

Solution:

Complexity Analysis:

Intuition:

Approach:

Dry Run:

Solution:

Complexity Analysis:

Frequently Occurring Doubts

Interview Followup Questions

Notes

Code