✅[Python] Simple and Clean, beats 88%✅
Please upvote if you find this helpful. \u270C\n\n\nThis is an NFT\n# Intuition\nThe problem asks us to find an edge in a graph that can be removed to make it a
### Please upvote if you find this helpful. \u270C\n<img src="https://assets.leetcode.com/users/images/b8e25620-d320-420a-ae09-94c7453bd033_1678818986.7001078.jpeg" alt="Cute Robot - Stable diffusion" width="200"/>\n\n*This is an NFT*\n# Intuition\nThe problem asks us to find an edge in a graph that can be removed to make it a tree. A tree is an undirected graph that is connected and has no cycles. So, we need to find an edge that creates a cycle in the graph. One way to detect cycles in an undirected graph is to use the `Union-Find algorithm.`\n\n# Approach\n1. Initialize the `parent` array with each node being its own parent and the `rank` array with all elements set to 1.\n2. Define the `find` function that takes a node as input and returns its root parent using path compression.\n3. Define the `union` function that takes two nodes as input and merges their sets if they are not already in the same set. The function returns `False` if the two nodes are already in the same set (i.e., there is a cycle), otherwise it returns `True`.\n4. Iterate over each edge in the `edges` array and call the `union` function with the two nodes of the edge as input.\n5. If the `union` function returns `False`, return the current edge as it creates a cycle in the graph.\n\n# Complexity\n- Time complexity: $$O(n \\alpha(n))$$ where $$n$$ is the number of nodes in the graph and $$\\alpha(n)$$ is the inverse Ackermann function which grows very slowly and can be considered a constant for all practical purposes.\n- Space complexity: $$O(n)$$ where $$n$$ is the number of nodes in the graph.\n\n# Code\n```\nclass Solution:\n    def findRedundantConnection(self, edges: List[List[int]]) -> List[int]:\n        # Initialize the parent array with each node being its own parent\n        # and the rank array with all elements set to 1\n        parent = [i for i in range(len(edges)+1)]\n        rank = [1]*(len(edges)+1)\n        \n        # Define the find function that takes a node as input\n        # and returns its root parent using path compression\n        def find(n):\n            p = parent[n]\n            while p != parent[p]:\n                parent[p] = parent[parent[p]]\n                p = parent[p]\n            return p\n        \n        # Define the union function that takes two nodes as input\n        # and merges their sets if they are not already in the same set\n        # The function returns False if the two nodes are already in the same set (i.e., there is a cycle)\n        # otherwise it returns True\n        def union(n1,n2):\n            p1,p2 = find(n1),find(n2)\n            if p1==p2:\n                return False\n            if rank[p1]>rank[p2]:\n                parent[p2]=p1\n                rank[p1]+=rank[p2]\n            else:\n                parent[p1]=p2\n                rank[p2]+=rank[p1]\n            return True\n        \n        # Iterate over each edge in the edges array and call the union function with the two nodes of the edge as input\n        for n1,n2 in edges:\n            if not union(n1,n2):\n                # If the union function returns False, return the current edge as it creates a cycle in the graph\n                return [n1,n2]\n```
['Union Find', 'Graph', 'Python', 'Python3']