Shortest Cycle in a Graph

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

from collections import defaultdict, deque
from typing import List

class Solution:
    def findShortestCycle(self, n: int, edges: List[List[int]]) -> int:
        adjacency_list = defaultdict(set)
        for u, v in edges:
            adjacency_list[u].add(v)
            adjacency_list[v].add(u)
        shortest = float('inf')
        for i in range(n):
            dq, distance, parent = deque([i]), [float('inf')] * n, [-1] * n
            distance[i] = 0
            while dq:
                node = dq.popleft()
                for kid in adjacency_list.get(node, set()):
                    if distance[kid] == float('inf'):
                        distance[kid] = distance[node] + 1
                        parent[kid] = node
                        dq.append(kid)
                    elif parent[kid] != node and parent[node] != kid:
                        shortest = min(shortest, distance[node] + distance[kid] + 1)
        return -1 if shortest == float('inf') else shortest