#785

Is Graph Bipartite?

specialist · 730 · lc medium +31 · verified · 58.9% accepted · 9,192 likes · top 56%

Description

You are given an undirected graph with n nodes (numbered 0 to n-1) represented by the adjacency list graph (no self-edges, no parallel edges, possibly disconnected). A graph is bipartite if its nodes can be split into two disjoint sets such that every edge connects a node from one set to a node from the other.

Return true if the graph is bipartite, false otherwise.

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}.

Code

1

2

3

class Solution:
    def isBipartite(self, graph: List[List[int]]) -> bool:

class Solution:
    def isBipartite(self, graph: List[List[int]]) -> bool: