Video Solution
By David Zhou
Video Solution Code
Explanation
Let's consider a simpler problem: given a graph, find the shortest cycle that passes through node 1.
What does a cycle through node 1 look like? In any cycle through node 1, there exists two nodes and on that cycle such that there is a path from 1 to and 1 to , and there is an edge between and . The length of this cycle is .
One might now try to use BFS to find for each in time and then check for each edge whether is minimal.
Of course, this means that we might count a "cycle" like . However, this doesn't matter for our original problem, since the shortest cycle will always be shorter than such a "cycle".
There's one problem with this approach though: if the edge is on the path from node 1 to node , then isn't a cycle! And this time, it does matter in our original problem!
Fortunately, there's a relatively simple fix.
Instead of first finding all and then checking for the minimum, do both at the same time during the BFS.
Now to prevent "backtracking", we only consider as a minimum if we're currently at node and .
This algorithm runs in time. Since and are so small, we can just apply this algorithm for all nodes instead of just node 1.
The final complexity of this solution is thus .
Implementation
C++
#include <algorithm>#include <cstring>#include <iostream>#include <queue>#include <vector>using namespace std;const int maxn = 2510;const int inf = 1000000007;
Optional: A Faster +1-Approximation
Can we improve the time complexity of the solution above when ? The solution code below reduces the time complexity to by breaking whenever the BFS visits the same vertex twice. However, it is possible that it returns the length of the shortest cycle plus one instead of the length of the shortest cycle exactly, so it does not pass all the tests on CSES.
#include <bits/stdc++.h>using namespace std;int main() {ios::sync_with_stdio(false);cin.tie(nullptr);int n, m;cin >> n >> m;
Join the USACO Forum!
Stuck on a problem, or don't understand a module? Join the USACO Forum and get help from other competitive programmers!