So it is O(N) in space?
I'm not sure we're talking about the same thing. I mean space requirements for the results of preprocessing.
Preprocessign itself may require computing cluster for all I care.
We are.
> But you can just write for each cell the index of component it belongs to. It can't belong to many, right?
Right. Each cell belongs to 1 and only 1 connected component.
However, there can be O(n) connected components overall. Think of a grid of cells all blocked off from each other, for instance.
As such, storing which connected component a cell belongs to technically requires O(log n) space, worst-case. Which means have overall you have n cells each requiring O(log n) space, or O(n log n) space overall.
In practice you can treat this as effectively O(n), however.
In practice you can treat it as O(1) time and O(n) space, though.
Also, that preprocessing with result saving is substantially slower than the connectivity alone. The connectivity alone is O(n) / O(n log n) preprocessing time - you check each cell a maximum of 5 / 9 times (depending on 4 or 8 way connectivity).
Also, that preprocessing with result saving fails miserably when you do updates to the graph.