Python | Simple Union-Find | O(n), O(n) | Beats 100%
CodeComplexity

Time complexity: O(n). Iterating over edges is O(n). Find_root uses path compression and is α(n), simplifies to constant.


Space complexity: O(
# Code
```python3 []
class Solution:
    def findRedundantConnection(self, edges: List[List[int]]) -> List[int]:
        root = list(range(len(edges) + 1)) # each node is root of own subtree

        def find_root(node):
            if root[node] != node:
                root[node] = find_root(root[node]) # set root for node as root of subtree
            return root[node] # found root of subtree

        for node1, node2 in edges: 
            root1, root2 = find_root(node1), find_root(node2)

            if root1 == root2:
                return [node1, node2] # both nodes are already in same subtree
 
            root[root2] = root1 # found new connection between nodes / subtrees
            # root[root1] = root2 also works            
```

# Complexity
- Time complexity: $$O(n)$$. Iterating over edges is O(n). Find_root uses path compression and is α(n), simplifies to constant. 

- Space complexity: $$O(n)$$. Root is O(n). Maximum recursion depth is each node or O(n).

# Performance

![Screenshot (833).png](https://assets.leetcode.com/users/images/3d85c3d6-8503-4e36-a6f5-f5f374796e09_1738112973.7964656.png)

['Depth-First Search', 'Union Find', 'Python3']