Set Union Data Structure
N chef’s are there. Each chef has a dish which is given a value (denoted by S*). You need to answer 2 queries :
- 0 x y : Chef containing dish x competes with chef containing dish y. If both dishes belong to same chef print “Invalid Query!” , otherwise the winner of the round will obtain all the dishes of the loser which will then be eliminated.
- 1 x : Output the chef which contains the dish x.
This problem can be solved using Disjoint set data structures.
Union Find or Disjoint Set Data structures allow you to merge two sets of items together dynamically and maintain for each item - to which set set does it belong.
This is exactly what we need in the problem , i.e. dynamically merging two sets and querying which set does an element belong.
We will be using Disjoint Set Data Structure that supports the following :
- find(A) : Get the id of the disjoint set to which A belongs(i.e. the chef id which contains that dish).
- union(A,B) : Merge the two disjoint sets in which A and B belong respectively.
Initially, we will create N disjoint set , each set contains 1 dish and it’s owner.
Let dish x be in setA and dish y be in setB.
If the dish contained by the owner of setA has score higher than the dish contained by the owner of setB , then we will merge setA and setB and set the owner of setA as the overall owner of the merged set.
If the dish contained by the owner of setB has score higher than the dish contained by the owner of setA , then we will merge setA and setB and set the owner of setB as the overall owner of the merged set.
Note : You can easily prove from this that the owner of the set has dish whose score is higher than all other dish of the set.
We will be using only Path Compression heuristics to solve the problem.
Initialize parent* = i Let S* denote the initial array. int find(int i) int j if(parent*==i) return i else j=find(parent*) //Path Compression Heuristics parent*=j return j set_union(int i,int j) int x1,y1 x1=find(i) y1=find(j) //parent of both of them will be the one with the highest score if(S[x1]>S[y1]) parent[y1]=x1 else if ( S[x1] < S[y1]) parent[x1]=y1 solve() if(query == 0) Input x and y px = find(x) py = find(y) if(px == py) print "Invalid query!" else set_union(px,py) else Input x. print find(x)