The SaaS offering came later. I used to run it on-prem a few years ago before the SaaS showed up and it was very low maintenance. More of a fire and forget situation once it was set up.
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.