785. Is Graph Bipartite?

Problem Statement

link: LeetCode.cn LeetCode

There is an undirected graph with n nodes, where each node is numbered between 0 and n - 1. You are given a 2D array graph, where graph[u] is an array of nodes that node u is adjacent to. More formally, for each v in graph[u], there is an undirected edge between node u and node v. The graph has the following properties:

There are no self-edges (graph[u] does not contain u). There are no parallel edges (graph[u] does not contain duplicate values). If v is in graph[u], then u is in graph[v] (the graph is undirected). The graph may not be connected, meaning there may be two nodes u and v such that there is no path between them. A graph is bipartite if the nodes can be partitioned into two independent sets A and B such that every edge in the graph connects a node in set A and a node in set B.

Return true if and only if it is bipartite.

Example:

Input: graph = [[1,2,3],[0,2],[0,1,3],[0,2]] Output: false

Input: graph = [[1,3],[0,2],[1,3],[0,2]] Output: true

Constraints:

graph.length == n 1 <= n <= 100 0 <= graph[u].length < n 0 <= graph[u][i] <= n - 1 graph[u] does not contain u. All the values of graph[u] are unique. If graph[u] contains v, then graph[v] contains u.

Solution Approach

The algorithm uses depth-first search (DFS) to attempt to color the graph with two colors, ensuring that no two adjacent nodes share the same color, which confirms if the graph is bipartite.

Algorithm

1. DFS Coloring: The algorithm uses depth-first search (DFS) to color each node with one of two colors, alternating colors for adjacent nodes to check for bipartiteness.
2. Bipartite Check: During the DFS traversal, if an adjacent node has the same color as the current node, the graph is not bipartite, and the algorithm marks it as invalid.
3. Handling Multiple Components: The algorithm iterates through all nodes to ensure that even disconnected components are checked, starting a new DFS for any uncolored nodes to verify bipartiteness across the entire graph.

Complexity

time complexity: O(V + E)V is the number of vertices. E is the number of edges. space complexity: O(V)

Implement

    class Solution:
    def isBipartite(self, graph: List[List[int]]) -> bool:
        def dfs(v, c):
            color[v] = c
            for node in graph[v]:
                if color[node] == c:
                    return False
                if color[node] == 0 and not dfs(node, -c):
                    return False
            return True
        
        l = len(graph)
        color = [0] * l
        for i in range(l):
            if color[i] == 0:
                if not dfs(i, 1):
                    return False
        return True
class Solution:
    def isBipartite(self, graph: List[List[int]]) -> bool:
        n = len(graph)
        UNCOLORED, RED, GREEN = 0, 1, 2
        color = [UNCOLORED] * n
        valid = True

        def dfs(node: int, c: int):
            nonlocal valid
            color[node] = c
            cNei = (GREEN if c == RED else RED)
            for neighbor in graph[node]:
                if color[neighbor] == UNCOLORED:
                    dfs(neighbor, cNei)
                    if not valid:
                        return
                elif color[neighbor] != cNei:
                    valid = False
                    return

        for i in range(n):
            if color[i] == UNCOLORED:
                dfs(i, RED)
                if not valid:
                    break
        
        return valid

    
    

Twitter  facebook  Email