Python by union-find [w/ Visualization]
Python by union-find (also known as disjoint set data structure)\n\n---\n\nHint:\n\nFind the redudant connection by picking the edge which forms a cycle in grap
Python by **[union-find](https://en.wikipedia.org/wiki/Disjoint-set_data_structure)** (also known as **[disjoint set](https://en.wikipedia.org/wiki/Disjoint-set_data_structure)** data structure)\n\n---\n\n**Hint**:\n\nFind the redudant connection by **picking the edge which forms a cycle** in graph G\n\n---\n\n**Visualization and Diagram**:\n\n![image](https://assets.leetcode.com/users/images/c4642d99-8107-4d7a-b17c-b3826e4d7724_1600410677.277295.png)\n\n---\n\n![image](https://assets.leetcode.com/users/images/f4c61e49-b0bf-4074-8294-4d3cce78b917_1600410693.4127119.png)\n\n---\n\n![image](https://assets.leetcode.com/users/images/d91a57a7-a20c-4c47-9c6f-c38d9f5e47f2_1600410707.5575693.png)\n\n---\n\n![image](https://assets.leetcode.com/users/images/46b7ec2f-bb08-4a43-a827-2ceb7e835565_1600410720.2455947.png)\n\n\n---\n\n**Implementation** by union-find:\n\n```\nclass Solution:\n    def findRedundantConnection(self, edges: List[List[int]]) -> List[int]:\n        \n        parent = {v:-1 for v in range(1, len(edges)+1)}\n        \n        # ---------------------------------\n        \n        def find(u):\n            \n            if parent[u] != -1:\n                # find root with path compression\n                parent[u] = find(parent[u])\n                return parent[u]\n            \n            else:\n                # root node must be with -1\n                return u\n            \n        \n        # ---------------------------------\n        \n        def union(u, v):\n\n           \n            parent_of_u = find(u)\n            parent_of_v = find(v)\n            \n            if parent_of_u == parent_of_v:\n                \n                # u and v has the same parent node\n                # this edges froms a cycle in graph\n                return True\n            \n            \n            else:\n                \n                # after adding edge(u, v)\n                # graph is still a tree without cycle\n                parent[parent_of_u] = parent_of_v\n                return False\n            \n        \n        # ---------------------------------\n        \n        redundant = None\n        for u, v in edges:\n                        \n            if union(u, v):\n                # check if edge (u, v) forms a cycle\n                redundant = [u, v]\n                return redundant\n        \n        \n```
['Union Find', 'Graph', 'Iterator', 'Python', 'Python3']