aboutsummaryrefslogtreecommitdiffstats
path: root/dotsandboxes/dataStructures.py
diff options
context:
space:
mode:
authorMatt Strapp <strap012@umn.edu>2021-04-26 17:12:01 -0500
committerMatt Strapp <strap012@umn.edu>2021-04-26 17:12:01 -0500
commita093060b0e8a787e51212b5f2879dc839605da65 (patch)
tree7ec2d69219d41ae6447efc41ebaaac34c696984b /dotsandboxes/dataStructures.py
parentRefactor jsut about everything (diff)
downloadcsci4511w-a093060b0e8a787e51212b5f2879dc839605da65.tar
csci4511w-a093060b0e8a787e51212b5f2879dc839605da65.tar.gz
csci4511w-a093060b0e8a787e51212b5f2879dc839605da65.tar.bz2
csci4511w-a093060b0e8a787e51212b5f2879dc839605da65.tar.lz
csci4511w-a093060b0e8a787e51212b5f2879dc839605da65.tar.xz
csci4511w-a093060b0e8a787e51212b5f2879dc839605da65.tar.zst
csci4511w-a093060b0e8a787e51212b5f2879dc839605da65.zip
Revert "Refactor jsut about everything"
This reverts commit e58a60ed18bde5db28ba96910df518a61b3999b2.
Diffstat (limited to 'dotsandboxes/dataStructures.py')
-rw-r--r--dotsandboxes/dataStructures.py32
1 files changed, 0 insertions, 32 deletions
diff --git a/dotsandboxes/dataStructures.py b/dotsandboxes/dataStructures.py
deleted file mode 100644
index 1e972fc..0000000
--- a/dotsandboxes/dataStructures.py
+++ /dev/null
@@ -1,32 +0,0 @@
-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