Find the Shortest Cycle in an Undirected Graph
You are given an undirected graph containing n vertices numbered from 0 to n - 1. Each edge is represented by a string in the format "u,v", indicating an undirected edge between vertices u and v.
Find and return the number of edges in the shortest cycle. A cycle begins and ends at the same vertex without using any edge more than once. Return -1 if the graph does not contain a cycle.
There is at most one edge between any pair of vertices, and no vertex has an edge to itself.
Method Signature
int shortestCycle(int n, List<String> edges)
Parameters
n
The number of vertices in the graph. The vertices are numbered from 0 to n - 1.
edges
A list of strings representing the undirected edges. Each string has the format "u,v", where u and v are the endpoints of an edge.
Return Value
Return the length of the shortest cycle in the graph. Return -1 when no cycle exists.
Constraints
2 ≤ n ≤ 1,0001 ≤ edges.size() ≤ 1,000- Every entry in
edges has the format "u,v".
0 ≤ u < n0 ≤ v < nu != v- No two entries represent the same undirected edge.
Examples
Example 1
shortestCycle(n = 5, edges = ["0,1", "1,2", "2,3", "3,0", "0,2"])
Output: 3
The edges connecting vertices 0, 1, and 2 form the shortest cycle: 0 → 1 → 2 → 0.
Example 2
shortestCycle(n = 6, edges = ["0,1", "1,2", "2,3", "3,0", "4,5"])
Output: 4
Vertices 0, 1, 2, and 3 form the shortest cycle, which contains four edges.
Example 3
shortestCycle(n = 5, edges = ["0,1", "1,2", "1,3", "3,4"])
Output: -1
The graph contains no cycle.