Biconnected Components

Genuine question: why do people sometimes write comments like this instead of Googling? Two guesses I have:

- HN responses might contain more first-hand experience and thus be richer than what one could find via Google or an LLM.

- Some terms are contextual so Google might not give the right answer, and an LLM could give a more contextual answer but might still just be wrong.

Are those usually the reason, or are there other reasons as well?

It's similar to math olympiad, but for algorithms.

Basically you get a bunch of problems (ranging from "check if a number is prime" to complicated graph theoretical problems) and some time to figure them out and code a correct & efficient solution. Often there are computer science concepts and reasoning techniques you need to know about (like biconnected components) to figure out how to make an efficient enough implementation.

The contests I used to go to, you got 11-13 problems and 5 hours to solve them with a team of 3. However, you only have one PC to share, so a lot of the time you are discussing, drawing stuff on paper and figuring out the solution in your head. There is also a printing service during the contest where you can literally get a paper version of your code :) so somebody else can code while you debug on paper.

See for instance https://www.acmicpc.net/category/detail/4319 for the kinds of problems they give (Korean website unfortunately but the problems are in English).

Whoops, you got me. Fixed!

At some point I relabeled the vertices to match the DFS order, but I must have forgotten to update this example.

The Boost algorithm computes the vertex-biconnected components rather than the edge-biconnected components, which are two different but related concepts. Articulation points are also more related to vertex-biconnectedness than to edge-biconnectedness (articulation points are vertices that lie in multiple vertex-biconnected components, i.e., if you remove one you split up the graph into more components). From what I can see in the Boost docs, it doesn't have an implementation of edge-biconnected components.

You can write an algorithm to compute all of the articulation points & bridges & edge-biconnected components & vertex-biconnected components in a single DFS. Because of this you refer to all of them as just "Tarjan's algorithm" even if you just compute one of them (he is kind of the Euler of graph algorithms in that like half of graph algorithms is named after him). So, on a technical level, I guess my implementation is similar to the algorithm in Boost because they both use DFS and this `low` map, but they compute different things.

Finding the vertex-biconnected components next to the articulation points involves more work though (the implementation I used to have manages to also do it in the same pass but also maintains a stack of edges).