Detect when a graph has been broken into two or more connected components

Question

I have a computer science problem that I've been thinking a lot about lately, and I'd be interested to hear other people's feedback:

Let's say you have a 3d blockworld (like minecraft). The world is "stable" if, for any block, there exists a solid path from that block to the bottom-most row of blocks. When the world is generated, it's guaranteed to be stable, but as players go around digging up the blocks, they could make the world unstable. For example, the player could dig out the trunk of a tree, in which case the top of the tree would be hovering in midair, and thus the world is unstable.

The goal is to quickly figure out if the world becomes unstable as the result of a dig, and which cubes should be removed to restore the world to a stable state. The algorithm should be fast and work in the context of a world where many digs are taking place, most of which do not make the world unstable.

One naive approach would be to take each adjacent cube after a dig and find a path to the bottom of the earth. If you can't find a path to the bottom from any of the neighbors, the world is now unstable (and you also learn which cubes to remove as part of the process). This falls apart when the path to the bottom is very long. It's pretty easy to come up with an example where this becomes computationally expensive (Imagine removing the top of a large, winding tower).

This problem can be thought of as a graph problem where you want to quickly detect if a single vertex can divide the graph into two or more components.

I'm interested to hear if anyone has other ideas of ways to make this problem tractable.

Answer 1

Link/cut tree may help you. Daniel Sleator, on of the authors of that structure shared his solution to the similar problem. Look his comments on codeforces.ru you may find them useful.

I would write here my idea. Let's create one vertex under the bottom level. This vertex is the basement of your building. Connect basement_vertex with all vertices at the bottom level. Run depth first search (DFS) from basement vertex. This dfs will produce rooted tree. This tree should be base (initial stage) of some link-cut tree.

UPDATE

Link-Cut Trees works only when given graph is a tree. For any graph we have to solve dynamic connectivity problem. Here more info about dynamic connectivity problem.

Answer 2

I would consider storing if each block is "unstable-if-dug", also known as a cut-vertex or biconnected component. Then you can look it up in constant time when clicked.

Basically, the idea is to be able to immediately know if it's stable. Then you recompute the graph while waiting for your next user input. The user experience is smoother, and unless somebody is clicking very fast, they shouldn't ever notice a slowdown.

You can find all a graph's cut vertices in O(n) time with a DFS.

From Wikipedia on biconnected components:

The idea is to run a depth-first search while maintaining the following information:

• the depth of each vertex in the depth-first-search tree (once it gets visited)
• for each vertex v, the lowest depth of neighbors of all descendants of v in the depth-first-search tree, called the lowpoint.

The lowpoint of v can be computed after visiting all descendants of v ... as the minimum of :

• the depth of v
• the depth of all neighbors of v (beside the parent of v in the depth-first-search tree)
• the lowpoint of all children of v in the depth-first-search tree.

The key fact is that a nonroot vertex v is a cut vertex (or articulation point) separating two biconnected components if and only if there is a child y of v such that lowpoint(y) ≥ depth(v).

The root vertex must be handled separately: it is a cut vertex if and only if it has at least two children.