Above is the most efficient known disjoint-set algorithm: Martin Rem's union-find.
Pretty sure the most efficient algorithm (it's linear) is to scan through the image in raster order but when you find a component you follow all the way around its border. I implemented it years ago. Can't remember the name though.