785. Is Graph Bipartite?

Medium

---

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 1:

Input: graph = [[1,2,3],[0,2],[0,1,3],[0,2]]
Output: false
Explanation: There is no way to partition the nodes into two independent sets such that every edge connects a node in one and a node in the other.

Example 2:

Input: graph = [[1,3],[0,2],[1,3],[0,2]]
Output: true
Explanation: We can partition the nodes into two sets: {0, 2} and {1, 3}.

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.

Approach :

A succesful completion of the 2-coloring of a bipartite graph will look like the following:

If at any point, we find that the node we are about to color with Yellow is already colored with Blue (or vice versa), this essentially means that the following non-bipartiteness exists:

class Solution:
    def isBipartite(self, graph: List[List[int]]) -> bool:
        self.graph = graph
        # Graph Coloring
        self.color = {}
        for index in range(len(graph)):
            if index not in self.color:
                # Initial Color of node is 0
                self.color[index] = 0
                # Call for DFS Traversal of this node
                if not self.dfs(index):
                    return False
        return True
        
    def dfs(self, index):
        # Traverse Adjacent Nodes
        for adj in self.graph[index]:
            # If Adjacent node is not colored yet, color it
            if adj not in self.color:
                self.color[adj] = 1 - self.color[index]
                # Call for this adjacent node DFS
                if not self.dfs(adj):
                    return False
            else:
                # If adjacent node is colored and having same color as node on other edge then 
                # it means they are in same setso return False
                if self.color[adj] == self.color[index]:
                    return False
        return True