I am a total newbie in disjoint-set so apologize in advance if this is a naive question. While I am going over the Explore Card, I am wondering whether we can optimize Quick Find so that we have node_id -> set_id -> root_id , this way, Find and Union will be both O(1) ? Attached please see my pseudo code in python.
class DisjointSet:
def __init__(self, edges):
set_map = {}
set_number = 0
set_head_map = {}
for node1, node2, in edges:
if node1 not in set_map and node2 not in set_map:
set_map[node1]=set_count
set_map[node2]=set_count
set_head_map[set_number]=node1
set_number+=1
elif node1 in set_map and node2 in set_map:
node1_head = set_head_map[set_map[node1]]
node2_set_number = set_map[node2]
set_head_map[node2_set_number]=node1_head
elif node1 in set_map:
node1_set_number = set_map[node1]
set_map[node2]=node1_set_number
elif node2 in set_map:
node2_set_number = set_map[node2]
set_map[node1]= node2_set_number
self.set_map=set_map
self._head_map=head_map
def connected(self, node1, node2):
if node1 not in set_map or node2 not in set_map:
return False
return set_head_map[set_map[node1]] == set_head_map[set_map[node2]]
def connected(node1, node2, disjoint_set)
return disjoint_set.connected(node1, node2)Thanks for your time
Comments (1)