# CS 271: Disjoint Set Naive Implementation (1.5 Points)

Developed by Professor Tralie and Professor Mongan.

# Exercise Goals

The goals of this exercise are:- To use instance methods in python
- To implement an ADT

Fill in the `find`

method in the naive bubble list implementation of disjoint sets below.

**Enter your Ursinus netid before clicking run. This is not your ID number or your email. For example, my netid is ctralie (non Ursinus students can simply enter their name to get this to run, but they won't get an e-mail record or any form of credit)**

Netid |

**If you are not on the campus network, you must be connected to the VPN for submission to be successful! You will receive a copy of your code via e-mail, so you'll know that it was submitted if you receive that e-mail!**VPN access requires Multi-Factor Authentication, which sends you a code when you log into the network. Instructions on configuring these for your account can be found here.

### Student Code

# List of lists, where each inner list corresponds to a bubble
class DJSet:
def __init__(self, N):
self.N = N
self.bubbles = []
for i in range(N):
self.bubbles.append([i])
#self.bubbles = [[i] for i in range(N)]
def _get_index_of(self, i):
ret = -1
idx = 0
found = False
while not found and idx < len(self.bubbles):
bubble = self.bubbles[idx]
for b in bubble:
if i == b:
ret = idx
found = True
idx += 1
return ret
def union(self, i, j):
"""
Void method that unions two elements
Parameters
----------
i: int
First element to union
j: int
Second element to union
"""
# Figure out what bubble i is in
idx_i = self._get_index_of(i)
# Figure out what bubble j is in
idx_j = self._get_index_of(j)
if idx_i != idx_j:
# Create a new bubble that merges the two
bubble = self.bubbles[idx_i] + self.bubbles[idx_j]
self.bubbles.append(bubble)
# Delete the original two bubbles
bubbles = []
for i in range(len(self.bubbles)):
if i != idx_i and i != idx_j:
bubbles.append(self.bubbles[i])
self.bubbles = bubbles
def find(self, i, j):
"""
A method that says if two elements belong to
the same set
Parameters
i: int
First element
j: int
Second element
Returns
-------
True if i and j belong to the same set, and False otherwise
"""
pass

### Test Code Block

# Run some tests on the class
s = DJSet(10)
s.union(0, 2)
s.union(1, 8)
s.union(8, 7)
print(s.find(0, 3), end='.')
print(s.find(1, 7), end='.')
s.union(1, 6)
s.union(0, 1)
print(s.find(0, 7), end='.')
print(s.find(1, 9))