CSES - Graph Girth

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

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

Of course, this means that we might count a "cycle" like $1\to x\to u\to v\to x\to 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)$ is on the path from node 1 to node $v$, then $1\to u\to v\to 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)$ 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)+1$ as a minimum if we're currently at node $u$ and $dist(1,u)\le dist(1,v)$.

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

1#include <bits/stdc++.h>
2using namespace std;
3 
4using ll = long long;
5using ld = long double;
6using db = double; 
7using str = string; // yay python!
8
9using pi = pair<int,int>;
10using pl = pair<ll,ll>;

1#include <bits/stdc++.h>
2using namespace std;
3 
4using ll = long long;
5using ld = long double;
6using db = double; 
7using str = string; // yay python!
8
9using pi = pair<int,int>;
10using pl = pair<ll,ll>;