[Python] Union-Find
This problem can easily be solved using the Union-Find (aka Disjoint-Set) data structure.\nUnion connects the parent nodes of two nodes. Find returns the deepes
This problem can easily be solved using the Union-Find (aka Disjoint-Set) data structure.\nUnion connects the parent nodes of two nodes. Find returns the deepest parent node of a node.\nUnion runs in ```O(1)``` and Find runs in ```O(a(n)) < O(5) = O(1)``` if union by rank/size is used in combination with path compression/halving/ splitting (see the proof on [Wikipedia](https://en.wikipedia.org/wiki/Disjoint-set_data_structure)).\n\nTo connect all n nodes in a graph at least n - 1 connections are needed. Therefore we can return -1 if that requirement is not met.\nUnite all nodes using the given connections. Then count how many disjoint groups of nodes there are: There is one group for every node that is its own parent. Subtract 1 and we get the number of required connections.\n\n**Shortest version without optimization techniques** (time: ```O(n + m * n)```, space: ```O(n)```)\n```python\nclass Solution:\n    def makeConnected(self, n: int, connections: List[List[int]]) -> int:\n        if len(connections) < n - 1:\n            return -1\n        \n        parent = list(range(n))\n        find = lambda x: x if parent[x] == x else find(parent[x])\n        \n        for a, b in connections:\n            parent[find(b)] = find(a)\n        \n        return sum(parent[x] == x for x in range(n)) - 1\n```\n\nTime complexity: ```O(n + m)``` (m is the number of connections)\nSpace complexity: ```O(n)```\n\n**Short version using union by rank and path splitting** (time: ```O(n + m)```, space: ```O(n)```)\n```python\nclass Solution:\n    def makeConnected(self, n: int, connections: List[List[int]]) -> int:\n        if len(connections) < n - 1:\n            return -1\n        \n        parent = list(range(n))\n        rank = [0] * n\n        \n        for a, b in connections:\n            while a != parent[a]:\n                a, parent[a] = parent[a], parent[parent[a]]\n            while b != parent[b]:\n                b, parent[b] = parent[b], parent[parent[b]]\n            \n            if rank[a] == rank[b]:\n                rank[a] += 1\n            elif rank[a] < rank[b]:\n                a, b, = b, a\n            \n            parent[b] = a\n        \n        return sum(parent[x] == x for x in range(n)) - 1\n```\n**Long OOP version using union by rank and path compression** (time: ```O(n + m)```, space: ```O(n)```)\n```python\nclass UnionFind:\n    def __init__(self):\n        self.parent = {}\n        self.rank = {}\n    \n    def union(self, a, b):\n        a, b = self.find(a), self.find(b)\n        \n        if a == b:\n            return\n        \n        if self.rank[a] == self.rank[b]:\n            self.rank[a] += 1\n        elif self.rank[b] > self.rank[a]:\n            a, b = b, a\n            \n        self.parent[b] = a\n    \n    def find(self, x):\n        if x not in self.parent:\n            self.parent[x] = x\n            self.rank[x] = 0\n        \n        if x != self.parent[x]:\n            self.parent[x] = self.find(self.parent[x])\n        \n        return self.parent[x]\n    \nclass Solution:\n    def makeConnected(self, n: int, connections: List[List[int]]) -> int:\n        if len(connections) < n - 1:\n            return -1\n        \n        uf = UnionFind()\n        \n        for i, j in connections:\n            uf.union(i, j)\n        \n        return sum(uf.find(x) == x for x in range(n)) - 1\n```
['Union Find', 'Python']