From e58a60ed18bde5db28ba96910df518a61b3999b2 Mon Sep 17 00:00:00 2001 From: Matt Strapp Date: Mon, 26 Apr 2021 17:06:13 -0500 Subject: Refactor jsut about everything --- dotsandboxes/dataStructures.py | 32 ++++++++++++++++++++++++++++++++ 1 file changed, 32 insertions(+) create mode 100644 dotsandboxes/dataStructures.py (limited to 'dotsandboxes/dataStructures.py') diff --git a/dotsandboxes/dataStructures.py b/dotsandboxes/dataStructures.py new file mode 100644 index 0000000..1e972fc --- /dev/null +++ b/dotsandboxes/dataStructures.py @@ -0,0 +1,32 @@ +class DisjointSet: + def __init__(self, nbElements): + self.parent = [] + self.rank = [] + for i in range(0, nbElements): + self.parent[i] = i + self.rank[i] = 0 + + 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): + xRoot = self.find(x) + yRoot = self.find(y) + + # x and y already belong to the same set + if xRoot == yRoot: + return + + # merge the set of x and y + if self.rank[xRoot] < self.rank[yRoot]: + self.parent[xRoot] = yRoot + elif self.rank[xRoot] > self.rank[yRoot]: + self.parent[yRoot] = xRoot + else: + self.parent[xRoot] = yRoot + self.rank[yRoot] += 1 + + def inSameSet(self, x, y): + return self.find(x) == self.find(y) \ No newline at end of file -- cgit v1.2.3