Graph coloring is NP-hard so it would be very difficult to replace it with an O(1) algorithm.

If you mean graph coloring restricted to planar graphs, yes it can always be done with at most 4 colors. But it could still be less, so the answer is not always the same.

(I know it was probably not a very serious comment but I just wanted to infodump about graph theory.)

You can't just put words in the author's mouth.

It's also not true at all. For instance, teaching in primary school is a field that is dominated by women where I live, and I (and I agree with the points described in the article) think it would be great to have more male teachers, so that girls and boys can both have rolemodels when growing up. This would also actually help to solve one of the problems that is described in the article, that boys feel unmotivated in school and fall behind.

Just because you think it is a good idea to have more male teachers doesn’t mean there is a push to have more male teachers. If there were, we would probably have more male teachers.

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

Thank you for the reply - appreciated.

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.

Nice. I'm liking the interactive diagrams!

I noticed another small error. Step 15 of the Tarjan's algorithm diagram reads:

> Since low[6] > 4, the edge is a bridge.

I think it should read:

> Since low[6] > low[4], the edge is a bridge.

That one is intentional. Note: a tree edge (u, v) is a bridge if and only if low[v] is strictly greater than the entry time of u.

Here 4 is the entry time of that node. (For convenience I made sure that the node labels are just the DFS entry times.)

Though maybe comparing both low values might also work, I'd have to think about that...

I used to get annoyed by these kinds of questions, but honestly I love talking about things I'm passionate about anyway and I want to get more people interested in the subject. So, I'm happy to answer questions like this and simultaneously sneak in some of my own personal experiences.

This is a nice attitude. I think HN is overall pretty nice for geeking out and also hearing other people geek out, but there is still a strain of elitism (not like StackExchange thankfully) and so I'm happy to see comments like this.

> there is still a strain of elitism

Those types can't help themselves so patterns emerge and usernames become recognizable after a while. There are some people who I just don't bother engaging with any more. Of course, those experiences are my own and maybe not the same experience as others.

Thanks, replies like yours are exactly why I prefer asking it here instead of googling.

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