day 25 optimize and improve heuristics

day 25 optimize and improve heuristics

My earlier algorithm assumes that the node with the most external
edges will always be on the other edge of the min-cut.  While it
worked for my input, it is fairly easy to construct a graph that
violates this property; several of the graphs at [1] went into an
inf-loop as a result.  Furthermore, it does O(n+e) work per iteration
determining the candidate node, and takes O(n) iterations (in reality,
closer to n/2 iterations); since the input is sparse enough that e is
approx 2n, this is roughly O(n^2) work, and trace shows 1135260 calls
to _round() and 843030 to visit().

The new algorithm takes a different approach: use two BFS to find two
distant nodes (a heuristic which happened to work for the sample, my
input, and all graphs at [1]); I suspect it is still possible to
construct a graph that violates my assumption, but I think it is
statistically less likely compared to my earlier heuristic.  Then,
with those nodes in hand, do 3 more BFS passes, removing the shortest
path between the two chosen nodes on each pass, in order to partition
the graph (assuming the two chosen nodes were indeed on opposite
sides) (not done here: I could short-circuit these BFS searches once
dst is found).  One more BFS search is then sufficient to count the
size on one side of the cut.  Since each BFS pass is O(n+e) work, and
I use only a constant number of passes, I have reduced the problem to
roughly O(n); trace shows a mere 59050 calls to v().  This speeds
things up to ~140ms.

[1] https://github.com/mattcl/unofficial-aoc2023-inputs/blob/master/day_025/solutions.md