Simplify Complexities

The problem is to find if a given edge (a, b) is connected in a graph with vertices {a, b, c, ...}.

Naive Solution – O(n^2)

• Maintain a parent array of size (len of vertex array)
• Update an edge (a, b) with the index a & b in the vertex array

ParentArray[a] = b
ParentArray[b] = b

Code

class Solution(object):
    def __init__(self, nodesCount):
        self.nodes = list(range(nodesCount + 1))

    def union(self, p, q):
        currentRoot = self.root(p)
        for index, num in enumerate(self.nodes):
            if num == currentRoot:
                self.nodes[index] = q
                
        print(self.nodes)

    def find(self, p, q):
        return self.root(p) == self.root(q)
    
    def root(self, p):
        return self.nodes[p]
    
if __name__ == "__main__":
    s = Solution(6)
    s.union(1, 2)
    s.union(2, 3)
    s.union(2, 4)
    
    print(s.find(1, 3))
    print(s.find(3, 4))
    print(s.find(3, 6))

Execution

$ python union-find.py 
[0, 2, 2, 3, 4, 5, 6]
[0, 3, 3, 3, 4, 5, 6]
[0, 4, 4, 4, 4, 5, 6]
True
True
False

Written with StackEdit.