[TheLoneWolfling]

> I'm not sure we're talking about the same thing.

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.

[ajuc]

So you treat 1 integer as log n? That's very technical, but in that case OK.

[TheLoneWolfling]

Yes. Although, as I said, in practice you can treat the integer index as constant space.