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