Best way to fusion two list of clusters Imagine the following sets :

A = Set( sortedSet(1,2,3), sortedSet(4,8))
B = Set( sortedSet(3,4), sortedSet(5,6,7) )


Where each inner list represent a cluster composed by indexed dots (1,2,3...).

I want to gather cluster sharing the dots sharing the same index into one to get :

Set( sortedSet(1,2,3,4,8), sortedSet(5,6,7) )


My first attempt was to merge two Sets

Set( sortedSet(1,2,3) ), sortedSet(3,4), sortedSet(4,8), sortedSet(5,6,7) )


and then merge each subset with subset of the same set where they share a common element. And repeat this process $k$ times with the result set until it doesn't change.

0 : Set( sortedSet(1,2,3,4), sortedSet(3,4,8), sortedSet(5,6,7) )
1 : Set( sortedSet(1,2,3,4,8), sortedSet(5,6,7) )
2 : Set( sortedSet(1,2,3,4,8), sortedSet(5,6,7) )
1 = 2 then Stop


Unfortunately i think this method is upperbounded in a bit less than $O(k.n^2)$ where n is the total number of elements in every subsets.

My second attempt was to get links which connected subsets of A and B.
Add to each A's subsets every sub sets of B which are connected to them from the link A -> B to get A'. Then use link B -> A to gathered A' subsets to get A''. Finally i apply my first attempt on A'' to get A''' and add it the lonely clusters in A and B.

So my final result is A''' + A_lonely + B_lonely

I use optimization that i know like using SortedSet and exist method (rather than go through each subset to know if they share a common element).

The second method works way faster (5min VS 45min) for a precise test.
But i know that i can still encounter the same issue due to the step A'' -> A''' which remains quadratic.

Any optimizations i could use or proper solution is welcome !
You could create an undirected graph which nodes are the clusters from A and B, two clusters being connected if they have a common dot. This graph can be built in time $O(n)$ where $n$ is the number of dots. Then the problem is to find the connected components of this graph. It is a standard problem that has a solution in linear time in terms of the number of edges and vertices of the graph. The clusters from each connected components are then fusioned to create the resulting clusters.