algoadvance

Leetcode 785. Is Graph Bipartite?

Problem Statement

You are given an undirected graph represented as a 2D array of integers graph, where graph[i] is a list of integers representing the nodes that node i is directly connected to. Determine if the given graph is a bipartite graph.

Clarifying Questions

  1. Input Constraints:
    • How large can the graph be? (i.e., number of nodes and edges)
    • Are there any self-loops or multiple edges between two nodes?
    • Is the graph guaranteed to be connected, or should we handle multiple components?
  2. Output:
    • Should the function return a boolean indicating if the graph is bipartite?
  3. Graph Representation:
    • How is the graph represented? Is it given as an adjacency list, or some other form?

Strategy

To determine if a graph is bipartite, we need to check if we can color the graph using two colors in such a way that no two adjacent nodes have the same color. This can be approached using a Breadth-First Search (BFS) or Depth-First Search (DFS).

Steps:

  1. Initialize:
    • Create a colors array to store the color assigned to each node, initialized to -1 (indicating no color assigned yet).
  2. Traversal:
    • For each unvisited node, perform BFS or DFS to attempt to color the graph.
    • If we find a situation where an adjacent node has the same color, the graph is not bipartite.

BFS Approach:

  1. Use a queue to process nodes.
  2. Start with an arbitrary node, color it with one color.
  3. For each visited node, color its neighbors with the opposite color.
  4. If a neighboring node already has the same color as the current node, return false.

Code

#include <vector>
#include <queue>

class Solution {
public:
    bool isBipartite(std::vector<std::vector<int>>& graph) {
        int n = graph.size();
        std::vector<int> colors(n, -1);
        
        // Iterate over all nodes to ensure we handle disconnected components
        for (int i = 0; i < n; i++) {
            if (colors[i] == -1) {
                if (!bfsCheck(graph, colors, i)) {
                    return false;
                }
            }
        }
        return true;
    }
    
private:
    bool bfsCheck(const std::vector<std::vector<int>>& graph, std::vector<int>& colors, int start) {
        std::queue<int> q;
        q.push(start);
        colors[start] = 0; // Start coloring the first node with color 0
        
        while (!q.empty()) {
            int node = q.front();
            q.pop();
            
            // Check all adjacent nodes
            for (int neighbor : graph[node]) {
                if (colors[neighbor] == -1) {
                    // Color the neighbor with the opposite color of the current node
                    colors[neighbor] = 1 - colors[node];
                    q.push(neighbor);
                } else if (colors[neighbor] == colors[node]) {
                    // An adjacent node has the same color
                    return false;
                }
            }
        }
        return true;
    }
};

Time Complexity

This approach ensures that we correctly determine if the graph is bipartite by attempting to color it using a BFS strategy and checking all nodes and edges efficiently.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI