D
DevExCode

LeetCode 785: Is Graph Bipartite? Solution

Master LeetCode problem 785 (Is Graph Bipartite?), a medium challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

Problem Explanation

Explanation:

To determine if a graph is bipartite, we can use graph coloring. The idea is to assign colors (let's say 0 and 1) to the nodes such that no two adjacent nodes have the same color. If we can color all nodes in this way, the graph is bipartite.

We can start by iterating through each node in the graph. For each uncolored node, we can perform a depth-first search (DFS) to color the node and its neighbors with the opposite color. If at any point we encounter a conflict (i.e., a neighbor with the same color as the current node), the graph is not bipartite.

After coloring all nodes, if we are able to color all nodes without any conflicts, then the graph is bipartite.

Algorithm:

  1. Initialize an array to store the color of each node. Use 0 and 1 for coloring.
  2. Iterate through each node in the graph.
  3. For each uncolored node, perform a DFS to assign colors to the node and its neighbors.
  4. During the DFS, if we encounter a conflict (neighbor with the same color as the current node), return false.
  5. If we are able to color all nodes without conflicts, return true.

Time Complexity:

The time complexity of this approach is O(V + E), where V is the number of vertices (nodes) and E is the number of edges in the graph.

Space Complexity:

The space complexity is O(V) for storing the colors of the nodes.

:

Solution Code

class Solution {
    public boolean isBipartite(int[][] graph) {
        int n = graph.length;
        int[] colors = new int[n];
        
        for (int i = 0; i < n; i++) {
            if (colors[i] == 0 && !dfs(i, 1, colors, graph)) {
                return false;
            }
        }
        
        return true;
    }
    
    private boolean dfs(int node, int color, int[] colors, int[][] graph) {
        colors[node] = color;
        
        for (int neighbor : graph[node]) {
            if (colors[neighbor] == color) {
                return false;
            }
            if (colors[neighbor] == 0 && !dfs(neighbor, -color, colors, graph)) {
                return false;
            }
        }
        
        return true;
    }
}

Try It Yourself

Loading code editor...

Related LeetCode Problems

Frequently Asked Questions

How to solve LeetCode 785 (Is Graph Bipartite?)?

This page provides optimized solutions for LeetCode problem 785 (Is Graph Bipartite?) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 785 (Is Graph Bipartite?)?

The time complexity for LeetCode 785 (Is Graph Bipartite?) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 785 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 785 in Java, C++, or Python.

Back to LeetCode Solutions