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.
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.