I implemented the Union-Find data structure and would love to receive some feedback about my code. I have just begun programming and welcome any feedback or constructive criticism which would improve my code quality and professionalism.
class UnionFind: def __init__(self, N=1001): self.N = N self.id = [i for i in range(self.N)] self._rank =  * self.N def __root(self, x): while x != self.id[self.id[x]]: self.id[x] = self.id[self.id[x]] x = self.id[x] return x def find(self, p, q): return self.__root(p) == self.__root(q) def unite(self, p, q): i = self.__root(p) j = self.__root(q) if self._rank[j] > self._rank[i]: i, j = j, i self.id[j] = i self._rank[i] += self._rank[j]
I was working on the problem of finding cycles in undirected graphs and realised union-find could be used to efficiently solve this problem and hence, implemented it.
In this instance the input would be a list of [u, v] pairs where u and v are integers and u < v. u and v are the node numbers of the graph under consideration.
For example the input [[1, 3], [2, 3], [1, 2]] would represent
The idea is as follows
iterate over the [u, v] pairs
if find(u, v): there exists a cycle since [u, v] belong to the same connected component
else: unite(u, v)
For the example graph [[1, 3], [2, 3], [1, 2]] above, the code would return on [1, 2] since adding this would result in a cycle.