You are viewing a single comment's thread. Return to all comments →
class DisjointSet: def __init__(self, arr = []): self.parent = {x : x for x in arr} self.rank = {x : 0 for x in arr} self.size = {x : 1 for x in arr} def find(self, x): if self.parent[x] != x: self.parent[x] = self.find(self.parent[x]) return self.parent[x] def union(self, x, y): if x not in self.parent: self.parent[x] = x self.rank[x] = 0 self.size[x] = 1 if y not in self.parent: self.parent[y] = y self.rank[y] = 0 self.size[y] = 1 rootX = self.find(x) rootY = self.find(y) if rootX != rootY: if self.rank[rootX] > self.rank[rootY]: self.parent[rootY] = rootX self.size[rootX] += self.size[rootY] elif self.rank[rootX] < self.rank[rootY]: self.parent[rootX] = rootY self.size[rootY] += self.size[rootX] else: self.parent[rootY] = rootX self.rank[rootX] += 1 self.size[rootX] += self.size[rootY] def componentsInGraph(gb): ds = DisjointSet() min_nodes = 15_001 max_nodes = 0 for x, y in gb: ds.union(x, y) for s in ds.size: if ds.parent[s] == s: if ds.size[s] > 1: min_nodes = min(min_nodes, ds.size[s]) max_nodes = max(max_nodes, ds.size[s]) return [min_nodes, max_nodes]
Seems like cookies are disabled on this browser, please enable them to open this website
I agree to HackerRank's Terms of Service and Privacy Policy.
Components in a graph
You are viewing a single comment's thread. Return to all comments →