


'''simple docstring'''

# A Bipartite Graph is a graph whose vertices can be divided into two independent sets,
# U and V such that every edge (u, v) either connects a vertex from U to V or a vertex
# from V to U. In other words, for every edge (u, v), either u belongs to U and v to V,
# or u belongs to V and v to U. We can also say that there is no edge that connects
# vertices of same set.
from queue import Queue



def 							SCREAMING_SNAKE_CASE__(		_UpperCamelCase   :					List[str] )		->       str:





   '''simple docstring'''







   UpperCamelCase__			    =    Queue()
   UpperCamelCase__			    =    [False] * len(_UpperCamelCase )
   UpperCamelCase__			    =    [-1] * len(_UpperCamelCase )

   def bfs():
      while not queue.empty():
         UpperCamelCase__			    =    queue.get()
         UpperCamelCase__			    =    True

         for neighbour in graph[u]:
            if neighbour == u:
               return False

            if color[neighbour] == -1:
               UpperCamelCase__			    =    1 - color[u]
               queue.put(_UpperCamelCase )

            elif color[neighbour] == color[u]:
               return False

      return True

   for i in range(len(_UpperCamelCase ) ):
      if not visited[i]:
         queue.put(_UpperCamelCase )
         UpperCamelCase__			    =    0
         if bfs() is False:
            return False

   return True


if __name__ == "__main__":
       # Adjacency List of graph
       print(check_bipartite({0: [1, 3], 1: [0, 2], 2: [1, 3], 3: [0, 2]}))



__lowerCamelCase   	=  {0: [1, 2], 1: [0, 3], 2: [0], 3: [1], 4: [5, 6], 5: [4, 6], 6: [4, 5]}

__lowerCamelCase   	=  {0: [1, 2, 3], 1: [0, 3], 2: [0], 3: [0, 1], 4: [], 5: []}



def 			_a      (    __UpperCamelCase	,	__UpperCamelCase	,	__UpperCamelCase			):
     a_     :  Tuple				      =     True
     a_     :  Optional[Any]				      =     []

     for neighbour in graph[vert]:
          if not visited[neighbour]:
               connected_verts += dfs(__UpperCamelCase	,	__UpperCamelCase	,	__UpperCamelCase			)

     return [vert, *connected_verts]



def 			_a      (    __UpperCamelCase			):
     a_     :  Dict				      =     len(__UpperCamelCase			)
     a_     :  List[str]				      =     graph_size * [False]
     a_     :  Dict				      =     []

     for i in range(__UpperCamelCase			):
          if not visited[i]:
               a_     :  str				      =     dfs(__UpperCamelCase	,	__UpperCamelCase	,	__UpperCamelCase			)
               components_list.append(__UpperCamelCase			)

     return components_list


if __name__ == "__main__":
       import doctest

       doctest.testmod()



