Given an adjacency list of a graph adj  of V no. of vertices having 0 based index. Check whether the graph is bipartite or not.
 
Example 1:
Input: 
Output: 1
Explanation: The given graph can be colored 
in two colors so, it is a bipartite graph.
Example 2:
Input:
Output: 0
Explanation: The given graph cannot be colored 
in two colors such that color of adjacent 
vertices differs. 
 
Your Task:
You don't need to read or print anything. Your task is to complete the function isBipartite() which takes V denoting no. of vertices and adj denoting adjacency list of the graph and returns a boolean value true if the graph is bipartite otherwise returns false.
 
Expected Time Complexity: O(V + E)
Expected Space Complexity: O(V)
Constraints:
1 ≤ V, E ≤ 10^{5}

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Graph algorithms

Data structures

Graph traversal

Starter code: class Solution:

	def isBipartite(self, V, adj):

		#code here

Solutions:
class Solution:

	def f(self, i, colour):
		q = []
		q.append(i)
		colour[i] = 0
		while q:
			var = q.pop()
			for neigh in adj[var]:
				if colour[var] == colour[neigh]:
					return False
				elif colour[neigh] == -1:
					colour[neigh] = 1 - colour[var]
					q.append(neigh)
		return True

	def isBipartite(self, V, adj):
		colour = [-1 for i in range(V)]
		for i in range(V):
			if colour[i] == -1:
				if self.f(i, colour) == False:
					return False
		return True


from collections import deque

class Solution:

	def dfs(self, node, V, adj, colored):
		colored[node] = 'red'
		q = deque()
		q.append((node, colored[node]))
		while q:
			(node, color) = q.popleft()
			for neighbor in adj[node]:
				if not colored[neighbor]:
					colored[neighbor] = 'blue' if color == 'red' else 'red'
					q.append((neighbor, colored[neighbor]))
				elif colored[neighbor] == colored[node]:
					return False
		return True

	def isBipartite(self, V, adj):
		colored = [0] * V
		for i in range(V):
			if not colored[i]:
				if not self.dfs(i, V, adj, colored):
					return False
		return True


from collections import deque

class Solution:

	def isBipartite(self, V, adj):
		color = [-1] * V

		def dfs(starNode, colorNow):
			color[starNode] = colorNow
			for nei in adj[starNode]:
				if color[nei] == -1:
					color[nei] = not colorNow
					if not dfs(nei, not colorNow):
						return False
				elif color[nei] == colorNow:
					return False
			return True
		for i in range(V):
			if color[i] == -1:
				if not dfs(i, 0):
					return False
		return True


from collections import deque

class Solution:

	def isBipartite(self, V, adj):
		color = [-1] * V

		def bfs(startNode):
			q = deque()
			color[startNode] = 0
			q.append(startNode)
			while q:
				node = q.popleft()
				for nei in adj[node]:
					if color[nei] == -1:
						color[nei] = not color[node]
						q.append(nei)
					elif color[nei] == color[node]:
						return False
			return True
		for i in range(V):
			if color[i] == -1:
				if not bfs(i):
					return False
		return True