Compute pair of similar list from a collection of lists
Build a hash of element -> list of lists that contain that element. From that it's easy to find all pairs of lists that share an element. Of course listing all pairs is still $O(n^2)$, since there might be quadratically many. But finding just $k$ pairs is $O(k+m)$, where $m$ is the total number of elements in all sets.