|
|
|
|
|
|
by throwaway43
3407 days ago
|
|
|
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. |
|
|
Just add everything one by one to a Disjoint set union.
My bad.