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 uu and vv on that cycle such that there is a path from 1 to uu and 1 to vv, and there is an edge between uu and vv. The length of this cycle is dist(1,u)+dist(1,v)+1dist(1, u) + dist(1, v) + 1.

One might now try to use BFS to find dist(1,i)dist(1, i) for each ii in O(N+M)\mathcal{O}(N + M) time and then check for each edge (u,v)(u, v) whether dist(1,u)+dist(1,v)+1dist(1, u) + dist(1, v) + 1 is minimal.

Of course, this means that we might count a "cycle" like 1xuvx11 \rightarrow x \rightarrow u \rightarrow v \rightarrow x \rightarrow 1. 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 (u,v)(u, v) is on the path from node 1 to node vv, then 1uv11 \rightarrow u \rightarrow v \rightarrow 1 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 dist(1,i)dist(1, i) and then checking for the minimum, do both at the same time during the BFS.

Now to prevent "backtracking", we only consider dist(1,u)+dist(1,v)+1dist(1, u) + dist(1, v) + 1 as a minimum if we're currently at node uu and dist(1,u)dist(1,v)dist(1, u) \leq dist(1, v).

This algorithm runs in O(N+M)\mathcal{O}(N + M) time. Since NN and MM 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 O(N(N+M))\mathcal{O}(N(N + M)).

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 MNM\gg N? The solution code below reduces the time complexity to O(N2)\mathcal{O}(N^2) 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!