Hi everyone.
Lets suppose that we have an array with differents elements, and a function f(x,y) that takes 2 elements from the array and return true or false..
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 vertex with value x to a vertex with value y 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
For graph with N vertices and M edges O(N + M) is best you can for this problem with BFS or DFS. May be there is some property in your graph. Better if you will give us a link of the problem.
The problem is not about dfs or bfs, but the build of the graph that will take O(n^2) . Sorry but i don't have an english version of this problem.
At least mention what the constraints are ( N, M, max number of queries, time limit, etc ).
Auto comment: topic has been updated by Mr.Awesome (previous revision, new revision, compare).
I'm not sure I understand this correctly, but if your job is to determine a graph with that operation, you will need O(n^2) operations anyway for some graphs. For example, if your graph is the isolated, with each node in its componen, you will need to check every pair to see whether there is an edge bewteen them, so searching for a better algorithm is pretty much useless. There may be faster solutions for certain classes of graphs.
I have the same feeling as you. In fact, IOI 2014 Game is a "proof" that it is not even sufficient to determine if the whole graph is connected or not without checking all pairs of nodes!
I think you can use Union Find to solve this problem. First root of every element is itself. Now iterate on the list of pairs having true relation and keep merging them. At last iterate the array and keep inserting root of every element in a set(to keep count of distinct elements). The size of this set is your answer. Hope it helps.
But generating all pairs will take O(n^2), right ?.
interesting you have to generate the list. Can you send link to the problem.
Sorry but i don't have an english version of this problem.
Well send the non-english version. There is always Google Translate.
I agree with [user:depevlad]there are some cases you have to do N^2. But if some wrote that problem maybe he said some condition that is the key. When we tell a problem to others, sometimes we leave out the most important condition that makes the problem doable. I think that has happened there, if you don't have an English version, give it to us anyway we will try to translate it without any loss. But what you have said so far seems to me that there is nothing special that can get you lower than the N^2. In example if the function f(x,y) tells you if x and y are in the same commponent .. that could be done more elegantly or efficient than N^2.