[MrHamdulay]

I would put each element from each set into a Disjoin-set data structure [1] and then report back all the sets whose elements all have cardinality 1.

The complexity of this data structure is pretty interesting. It basically comes to O(N) for N < any number that can be represented in the known universe. It's also the coolest use of the inverse ackermann function I've seen!

How to solve this on a distributed system I have no idea.

[1] https://en.wikipedia.org/wiki/Disjoint-set_data_structure