Hi everyone.
Lets suppose that we have an array a with some elements, and a function f(x,y) that takes 2 elements 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.