Disjoint Set

Challenge Given an adjency matrix, find the group of nodes that are connected together. E.g isConnected = [[1,1,0],[1,1,0],[0,0,1]] Will return 2 Data Structure Creating a Disjoin Set data structure using a dictionary. class DisjointSet: def __init__(self, n): self.rank = {i:i for i in range(n)} def __repr__(self): return f"Repr:{self.rank}" def find(self, val): # adding collapsing find original_v = val while self.rank[val] != val: val = self.rank[val] if original_v != val: self.rank[original_v] = val return val def union(self,val1, val2): v1 = self....

October 10, 2021 · 1 min · Nolan