Whoops, make that an O(log n) check, technically speaking, as the index of which CC a cell belongs to may take O(log n) space worst-case.

Though you can treat it as effectively O(1) time and O(n) space.