https://leetcode.com/problems/is-graph-bipartite

This problem is very similar to problem 886. Possible Bipartition and it happens that I already solved this problem previously, you can see my solution here: https://leetcode.com/problems/possible-bipartition/discuss/654840/Python-Simple-dfs-traversal-O(E%2BV)-detailed-explanations

Here I do absolutely the same idea, but with a bit more clear coding style and also we do not need to create adjacency list here, it is already given in this way. The idea is the following: we traverse our graph and color our nodes int two colors 0 and 1: first one for nodes which can be reached with even number of steps and 1 for odd number of steps. Also we keep self.loop flag, which is true if we found odd loop, that is our graph is not bipartite.

We define dist array with -1 inside and then we start dfs from every node, and color our graph (note, that graph can have several connected components, so we need to start dfs from all nodes).

Complexity: time complexity is O(E+V), because it is complexity of classical dfs we are using. Space complexity is O(V) to keep dist array. Here E is number of edges and V is number of vertices.

class Solution:
    def isBipartite(self, graph):
        def dfs(start):
            if self.loop: return     #early stop if we found odd cycle

            for neib in graph[start]:
                if dist[neib] >= 0 and dist[neib] == dist[start]:
                    self.loop = True
                elif dist[neib] < 0:
                    dist[neib] = dist[start]^1
                    dfs(neib)
            
        n = len(graph) 
        self.loop, dist = False, [-1] *(n)
        
        for i in range(n):
            if self.loop: return False     #early stop if we found odd cycle
            if dist[i] == -1:
                dist[i] = 0
                dfs(i)
                
        return True

If you like the solution, you can upvote it on leetcode discussion section: Problem 0785