Python | Union Find
Intuition\n Describe your first thoughts on how to solve this problem. \n\n# Approach\n Describe your approach to solving the problem. \n\n# Complexity\n- Time 
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\nclass Disjoint:\n    def __init__(self,n):\n        self.rank = [1 for i in range(n)]\n        self.parent = [i for i in range(n)]\n\n    def find(self,x):\n        if self.parent[x] == x:\n            return x\n        self.parent[x] = self.find(self.parent[x])\n        return self.parent[x]\n    \n    def union(self,u,v):\n        if self.find(u) == self.find(v):\n            return\n        \n\n        pu = self.find(u)\n        pv = self.find(v)\n        if self.rank[pu] > self.rank[pv]:\n            self.parent[pv] = pu\n        elif self.rank[pu] < self.rank[pv]:\n            self.parent[pu] = pv\n        else:\n            self.parent[pv] = pu\n            self.rank[pu] += 1\n\n\n\nclass Solution:\n    def makeConnected(self, n: int, connections: List[List[int]]) -> int:\n        ds = Disjoint(n)\n        extra = 0\n        for i in connections:\n            pu = ds.find(i[0])\n            pv = ds.find(i[1])\n            if pu == pv:\n                extra += 1\n            else:\n                ds.union(pu,pv)\n            \n        ans = 0\n        for i in range(n):\n            if ds.parent[i] == i:\n                ans += 1\n        \n        ans -= 1\n        if extra >= ans:\n            return ans\n        else:\n            return -1\n\n```
['Union Find', 'Python3']