Problem statement

https://binarysearch.com/problems/Detecting-an-Odd-Length-Cycle/

Solution

We just need to check if graph if bipartite.

Complexity

Time complexity is O(n + E), space is O(n).

Code

class Solution:
    def solve(self, graph):
        n = len(graph)
        color = [-1] * n

        for start in range(n):
            if color[start] == -1:
                color[start] = 0
                stack = [start]

                while stack:
                    parent = stack.pop()

                    for child in graph[parent]:
                        if color[child] == -1:
                            color[child] = 1 - color[parent]
                            stack.append(child)
                        elif color[parent] == color[child]:
                            return True

        return False