Problem statement

https://binarysearch.com/problems/Shortest-Cycle-Containing-Target-Node/

Solution

Here we need to carefully use bfs: traverse graph and mark nodes visited after we we visit all its neighbours.

Complexity

It is O(E + V) for time and O(V) for space.

Code

class Solution:
    def solve(self, graph, target):
        queue = deque([(0, target)])
        V = set()
        while queue:
            dep, cur = queue.popleft()
            if cur in V: continue
            for neib in graph[cur]:
                if neib == target: return dep + 1
                queue.append([dep + 1, neib])
            V.add(cur)

        return -1