1783. The Shortest Loop of Odd Length

An UNDIRECTED graph has n vertices and m edges, and no self-loops. A CYCLE is a closed walk that repeats no vertex and no edge, and its length is the number of edges in it. Print the length of the shortest cycle whose length is ODD, or -1 if the graph has no odd cycle.

triangle 1-2, 2-3, 3-1 -> 3 square 1-2, 2-3, 3-4, 4-1 -> -1 square plus the diagonal 1-3 -> 3 path 1-2, 2-3 -> -1 two rings, of 5 and of 7 -> 5

Problem 1782 prints a two-group split or says NO. A graph has such a split exactly when it has no odd cycle, so -1 here is the same condition as YES there. This problem asks HOW SHORT the obstruction is, which the split cannot tell you.

## What most people try first

Finding the shortest cycle and checking its parity. That is not merely slow, it is the wrong question, and it fails in BOTH directions.

a square alone shortest cycle 4, odd cycle: none -> -1 a square and a separate 5-ring shortest cycle 4, odd cycle: 5 -> 5

Those two graphs have the same shortest cycle length and different answers, so the length of the shortest cycle carries no information about this question at all. The two have to be asked separately.

The second attempt is a depth-first search that reports the first odd cycle it closes. That finds AN odd cycle, not the shortest, because a depth-first tree can descend a long way before closing anything. The third is to two-colour the graph and report the cycle the conflict sits on, which again is whatever cycle the traversal order happened to reach.

## Breadth first from every vertex

answer = min over start vertices s min over edges (u, v) dist(s,u) + dist(s,v) + 1, keeping only ODD totals

dist(s,x) is the number of edges on a shortest walk from s to x, which one breadth-first search from s gives for every x at once. Vertices s cannot reach are skipped.

## Why it is correct

Both directions.

NO UNDER-ESTIMATE. Suppose some s and some edge (u, v) give an odd total L = dist(s,u) + dist(s,v) + 1. Then walking a shortest route s to u, crossing the edge to v, and walking a shortest route back from v to s is a CLOSED WALK of length L, which is odd. A closed walk of odd length must contain an odd cycle: split the walk wherever it revisits a vertex, which breaks it into cycles whose lengths add up to L; if every one of those were even the total would be even, so at least one is odd, and it is no longer than L. So the true answer is at most L, and therefore at most the minimum of all such L.

NO OVER-ESTIMATE. Let C be a shortest odd cycle, of length L, and let s be any vertex on it. Walking round C from s in the two directions reaches each vertex of C, and since L is odd there is exactly one EDGE of C, say (u, v), whose two ends are at equal distance ALONG THE CYCLE from s, namely (L - 1) / 2 each. True distances in the graph are at most those cycle distances, so dist(s,u) + dist(s,v) + 1 <= L. It cannot be smaller than the true answer by the paragraph above, and the true answer is L, so the formula reports exactly L for this s and this edge.

## The boundaries that break a careless implementation

Only ODD totals count. An even total is a closed walk of even length and proves nothing, and taking the minimum over all totals returns 3 for a square with a parallel edge.

A vertex s cannot reach must be skipped, not treated as being at distance 0 or at a large distance that happens to be even. A graph is allowed to be in several pieces, and the shortest odd cycle may be in the last of them.

A PARALLEL EDGE is two edges between the same pair, so it is a cycle of length 2, which is even and so never the answer. It also never creates a spurious odd total, because the argument above turns any odd total into a genuine odd cycle.

m = 0 gives -1.

## Cost

One breadth-first search per start vertex, then one pass over the edges per start: O(n * (n + m)). At n = 300 and m = 2000 that is under a million steps. The searches are iterative by nature, since breadth-first uses a queue, so the recursion limit never comes into it.

## Overflow

A distance is at most n - 1, which is 299, and the answer is at most n. No quantity approaches the 32-bit signed limit of 2147483647.

## Worked example

``` edges: 1-2, 2-3, 3-4, 4-1, 1-3 (a square plus one diagonal)

search from s = 1: dist = [0, 1, 1, 1] edge (2,3): 1 + 1 + 1 = 3 ODD -> candidate 3 edge (1,2): 0 + 1 + 1 = 2 even -> ignored edge (3,4): 1 + 1 + 1 = 3 ODD -> candidate 3

answer: 3 (the triangle 1-2-3-1) ```

Constraints - `1 ≤ n ≤ 300` - `0 ≤ m ≤ 2000` - `1 ≤ u, v ≤ n` and `u ≠ v`, so there are no self-loops - repeated edges can occur: two edges between the same pair form a cycle of length 2, which is even and so never the answer - the graph may be disconnected, and the shortest odd cycle may lie in any piece