Detecting when a single group of blocks is broken into multiple groups

Let’s say you have an array of blocks (AABB), where each block is touching or intersecting any number of other blocks. Together they make up a larger object, and because they’re all touching, you can consider them to all be on the same “grid”. Each block can have any size or position, but is always axis-aligned.

Now let’s say you delete one of the blocks, somewhere in the middle, such that there is now a gap where blocks are no longer touching.

How would you go about detecting that you now have two clusters of blocks, two “grids”, instead of one?

My first thought is to loop through all blocks, perform AABB collision checks against all other blocks, mark the ones that touch, then recursively cycle through the touched blocks looking for others that touch, until you reach the end and can look for blocks that were not marked. But that sounds extremely inefficient.

This is in plain C, so I’m trying to keep memory use limited to the existing array of block structs.