#2608

Shortest Cycle in a Graph

master · 1725 · lc hard +32 · verified · 39.2% accepted · 625 likes · top 18%

⚑ DFS / BFS: Connected Components & Reachability

Description

You are given an undirected graph with n vertices labeled 0 to n - 1. Each edge is given by edges[i] = [ui, vi] — no self-loops or multi-edges exist. Return the length of the shortest cycle, or -1 if the graph is acyclic. A cycle starts and ends at the same vertex with each edge used at most once.

Example 1:

Input: n = 7, edges = [[0,1],[1,2],[2,0],[3,4],[4,5],[5,6],[6,3]]

Output: 3

Explanation: The cycle with the smallest length is : 0 -> 1 -> 2 -> 0

Example 2:

Input: n = 4, edges = [[0,1],[0,2]]

Output: -1

Explanation: There are no cycles in this graph.

Code

1

2

3

class Solution:
    def findShortestCycle(self, n: int, edges: List[List[int]]) -> int:

class Solution:
    def findShortestCycle(self, n: int, edges: List[List[int]]) -> int: