Hi everyone.

Lets suppose that we have an array a with some elements, and a function f(x,y) that takes 2 elementsfrom the array and return true if these elements are connected and false otherwise.

We want to extract all connected components.

Note that if f(x,y) = true and f(y,z) = true then x,y,z are in the same connected component even though f(x,z) = false

My simple solution is to iterate over each pair(x,y) and connect them if f(x,y) = true , and then extract all connected components.

The complexity of this solution is O(n^2) , However i'm looking for a better solution. Thanks.

UDP I guess i didn't explain well, so here an example :

Lets a be an array : a = { 1 , 4 , 7 , 5 , 9 }

f(1,4)=true , f(1,7)=false , f(1,5)=false , f(1,9)=false f(4,7)=false , f(4,5)=false , f(4,9)=true f(7,5)=true , f(7,9)=false f(5,9)=false

So the answer will be 2 sets ( 1,4,9 ) and (7,5)

Note that f(x,y)=f(y,x)

N=1e5