You could just go on merging sets with each other. For i from 0 to n-1 , find all sets from i+1 to n-1 which have a non empty intersection with set i. Union se

You could just go on merging sets with each other. For i from 0 to n-1 , find all sets from i+1 to n-1 which have a non empty intersection with set i. Union set i with all those sets and replace i with the union set. If you use a disjoint set data structure this will be quadratic or O(n^2) EDIT: On further thought you need to merge from the end and backwards.