Author: Kishore Kumar
DIFFICULTY:
SUPER-HARD
EXPLANATION:
The problem was with the low update in Tarjans. Intuitively it makes sense that the low update works because the condition for a node v to be an articulation point is simply checking if there exists a child node in the DFS tree such that there is no back edge from its bi-connected component to any node above v. In fact, this version of the update will work for the version of Tarjan’s where we are trying to identify bridges.
However, when trying to find articulation points, this update ignores articulation points when the back edge from a child’s bi-connected component passes through the articulation point itself.
Consider the case where the DFS order is 1, 2, 3, 4, 5
On the callback from 3, the low value of 2 is updated to the low value of 1. (Which was initially 1)
Now, when the DFS is at node 5, the low value of 5 is updated to the low value of 2 incorrectly. Due to this, the check for the articulation point at node 2 does not trigger even though the back edge from 5 passes through 2. The low update essentially implies that we can reach some parent node of 2 in the DFS tree from 5 via a back edge. But this ignores the fact that we are passing through the articulation point itself.
Now all that is left is to construct a similar case on the grid from the bottom right corner using the given DFS order. Here is one such hack case
10 16
................
.#######........
.#.....#........
.#.....#........
.#..##########..
.#..#..#.....#..
.#..####.....#..
.#...........#..
.#############..
................