In the past we had indexed color screen modes. You could draw all pixels to the screen once and give each pixel an index into a color palette. When you would start, they would all be mapped to white, but as you start with coloring, you would then just change the color of the palette entry (truly a O(1) operation) and your graphics card would then do the work at scan time. I guess the closest equivalent nowadays would be to do this inside the pixel shader.
This is however not the same operation, changing the palette will affect all pixel of that color, flood fill affects only all the pixels in the connected component you clicked on.
> changing the palette will affect all pixel of that color
Not necessarily, because same color doesn't require same palette index. If you are going to preprocess the image anyway, you can assign one palette index to each connected component.
