Disjoint set implementation in Python

Your program is not working correctly because you have misunderstood the algorithm for disjoint set implementation. Union is implemented by modifying the parent of the root node rather than the node provided as input. As you have already noticed, blindly modifying parents of any node you receive in input will just destroy previous unions.

Here's a correct implementation:

def union(self, set1, set2):
    root1 = self.find(set1)
    root2 = self.find(set2)
    self.parent[root1] = root2

I would also suggest reading Disjoint-set data structure for more info as well as possible optimizations.

To make your implementation faster, you may want to update the parent as you find()

    def find(self, item):
        if self.parent[item] == item:
            return item
        else:
            res = self.find(self.parent[item])
            self.parent[item] = res
            return res