Approach
Breadth-first search
For Shortest Cycle in a Graph, the implementation explores reachable states in layers, which is the standard shape for unweighted shortest paths and minimum-step transitions.
- Model each valid configuration as a state and each legal move as an edge.
- Seed the queue with the starting state and mark it immediately.
- Expand each state once, recording distance or reachability for unseen neighbours.
Code notes
- 44 lines of C++ from the credited upstream file 2608.cpp.
- The implementation visibly relies on sequence storage, work queue.
- 4 loop blocks detected.
Complexity
Verify that each state and transition is processed only a bounded number of times; that determines the traversal cost.
Check the problem constraints before deciding whether this complexity will pass.
Use this to learn the idea, then write your own version.
1class Solution {2 public:3 int findShortestCycle(int n, vector<vector<int>>& edges) {4 int ans = kInf;5 vector<vector<int>> graph(n);6 7 for (const vector<int>& edge : edges) {8 const int u = edge[0];9 const int v = edge[1];10 graph[u].push_back(v);11 graph[v].push_back(u);12 }13 14 for (int i = 0; i < n; ++i)15 ans = min(ans, bfs(graph, i));16 17 return ans == kInf ? -1 : ans;18 }19 20 private:21 static constexpr int kInf = 1001;22 23 24 25 int bfs(const vector<vector<int>>& graph, int i) {26 vector<int> dist(graph.size(), kInf);27 queue<int> q{{i}};28 dist[i] = 0;29 while (!q.empty()) {30 const int u = q.front();31 q.pop();32 for (const int v : graph[u]) {33 if (dist[v] == kInf) {34 dist[v] = dist[u] + 1;35 q.push(v);36 } else if (dist[v] + 1 != dist[u]) { 37 return dist[v] + dist[u] + 1;38 }39 }40 }41 return kInf;42 }43};44