CSES - Graph Girth

Authors: Benjamin Qi, Andi Qu


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)).

#include <algorithm>
#include <cstring>
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
const int maxn = 2510;
const int inf = 1000000007;

Optional: BFS-Cycle

We can modify the algorithm above to return either the length of the shortest cycle or the length of the shortest cycle plus one in O(N2)\mathcal{O}(N^2) time. See here for details.

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
using db = double;
using str = string; // yay python!
using pi = pair<int, int>;
using pl = pair<ll, ll>;

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!