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

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.

Om arbejdsgiveren:
( 0 bedømmelser ) Hyderabad, India

Projekt ID: #18013397

## Tildelt til:

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 Flere

\$30 USD på 1 dag
(0 bedømmelser)
0.0

## 9 freelancere byder i gennemsnit \$41 på dette 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 dage
(340 bedømmelser)
7.2
wizard2015

\$61 USD in 3 dage
(92 bedømmelser)
6.5
kipdev13

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.

\$35 USD på 1 dag
(32 bedømmelser)
4.9
\$30 USD på 1 dag
(1 bedømmelse)
0.4
sobankhan1144

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

\$30 USD på 1 dag
(0 bedømmelser)
0.0
Sanalmanikandan

one day requirement. .

\$30 USD på 1 dag
(0 bedømmelser)
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 på 1 dag
(0 bedømmelser)
0.0