bipartite graph

"""
algorithm:bfs
method: check whether vertex coloring==2?
-1------------------------->not visited
0 -------------------------> color 1
1-------------------------->color 2
"""


from collections import deque
class Solution:

    def isBipartite(self, V, adj):
        def bfs(src):
            q=deque()
            q.append(src)
            col[src]=0
            while q:
                t=q.popleft()
                for i in adj[t]:
                    if i==t:
                        return False
                    elif col[i]==-1:
                        col[i]=1-col[t]
                        q.append(i)
                    elif col[i]==col[t]:
                        return False
            return True

        #code here
        col=[-1]*V
        for i in range(V):
            if col[i]==-1 and not bfs(i):
                return False
        return True
'''
DFS version
'''
class Solution:
    def isBipartite(self, n, adj):
        cols=[-1]*n
        def dfs(u):
            for v in adj[u]:
                if cols[v]!=-1:#if unvisited
                    if cols[v]==cols[u]:
                        return False
                else:#if visited
                    cols[v]=1-cols[u]
                    if dfs(v)==False:return False
            return True
        for i in range(n):
            if cols[i]==-1:
                cols[i]=0
                if dfs(i)==False:return 0
        return 1