# build me a c code that takes a collection of disjoint singletons followed by set operations as mentioned in description.

Budget $10-30 USD

Goal: Serve the following requests:

– Given elements a and b, are they in the same set?

– Given an element a, what is the representative element of the set containing a?

– Given a and b, perform union of the sets that contain a and b.

– Given an element a, what is the rank of a?

Input Format

Each line of the input looks like one of the following:

• ‘N’ followed by a positive integer n that indicates number of singleton sets to create.

• ‘?’ followed by two positive integers a and b separated by a space.

• ‘S’ followed by a positive integer a.

• ‘U’ followed by two positive integers a and b separated by a space.

• ‘R’ followed by a positive integer a.

Each of the lines above ends with a ‘\n’ character. All numbers used will fit inside an int.

End of input is indicated by EOF.

Output Format

• If input line was “N n”: No corresponding output.

• If input line was “U a b”: No corresponding output.

• If input line was “? a b”:

– Output −1 if either of a or b is not a valid element.

– Output 0 if a and b belong to different sets.

– Output 1 if a and b belong to the same set.

1

• If input line was “S a”:

Output the representative element of the set that contains a.

• If input line was “R a”:

Output the rank of a if a is a valid element. Output −1 otherwise.

All output lines have to end with a ‘\n’ character.

Implementation rules

• When the request “N n” is given, you’ll create n singleton sets namely {1}, {2}, . . . , {n}

and each element will be the representative of its own singleton set. Discard the

previous collection of sets if any.

• The sets have to be stored using the disjoint forest implementation.

• Use an array of pointers to have random access to the node corresponding to each

element.

• When the request “U a b” is issued, let the sets containing a and b be Sa and Sb with

representative elements ra and rb respectively. You have to perform a union of the sets

Sa and Sb and remove Sa and Sb from your collection. The union operation has to

be implemented using the Union by Rank heuristic. Further, if ranks of ra and rb are

equal, you should make the tree corresponding to Sb a child of ra and thus increment

rank of ra.

• Do not use the Path Compression heuristic for Union.

## Awarded to:

I am student of Indian Institute of Technology (IIT) Jodhpur . Most reputed Institute of India. I have solved many of such questions many times . I will be able to complete the task within a day using disjoint set and More

## 9 freelancers are bidding on average $41 for this job

hi. i have a lot of experience in C/C++ programming. i can easily complete this project for you. we can have a chat. thanks

Hi, I am experienced programmer, and I can help you to implement this task. Please contact me if you are interested in cooperation.

Hello I have read your description. I am sure i can do your task perfectly. If you choose me, i can give you good result. i want to work with you.

I can do the job and you will not regret it if you hire me. I can do the job and you will not regret it if you hire me.

I can provide the algorithm with the solution in an efficient and elegant way in terms of code. I have experience in complex mathematical algorithms for signal processing, both in c and matlab