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

In Progress Posted 5 years ago Paid on delivery
In Progress Paid on delivery

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.

Algorithm C Programming C# Programming C++ Programming

Project ID: #18013397

About the project

6 proposals Remote project Active 5 years ago

Awarded to:

saurabhanonymus

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

$30 USD in 1 day
(0 Reviews)
0.0

6 freelancers are bidding on average $46 for this job

utkarshkatiyar19

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

$100 USD in 5 days
(415 Reviews)
7.4
wizard2015

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

$61 USD in 3 days
(96 Reviews)
6.5
sobankhan1144

Already done with the code. Accept the bid and get the code. Simple

$30 USD in 1 day
(0 Reviews)
0.0
Sparoow

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.

$30 USD in 1 day
(0 Reviews)
0.0
nikoacade95

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

$25 USD in 1 day
(0 Reviews)
0.0