Union Find. Simple solution (+ Topological sort, DFS)
Union Find
Time: O(n∗alpha(n)) where alpha(n) is the inverse Ackermann function
Space: O(n)

Topological sort
Time: O(n). Space: O(n)

DFS
Time: O(n). Space: O
1. Union Find
Time: $O(n*alpha(n))$ where $alpha(n)$ is the inverse Ackermann function
Space: $O(n)$
```
class UnionFind:
    def __init__(self, n: int):
        self.parent = [*range(n)]
        self.rank = [1] * n
   
    def find(self, x: int) -> int:
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]

    def union(self, x: int, y: int) -> None:
        x, y = self.find(x), self.find(y)
        if x == y:
            return True
        if self.rank[x] < self.rank[y]:
            self.parent[x] = y
        else:
            self.parent[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1
        return False
            

class Solution:
    def findRedundantConnection(self, edges: List[List[int]]) -> List[int]:
        uf = UnionFind(len(edges)+1)
        for u, v in edges:
            if uf.union(u, v):
                return [u, v]
```
2. Topological sort
Time: $O(n)$. Space: $O(n)$
```
class Solution:
    def findRedundantConnection(self, edges: List[List[int]]) -> List[int]:
        graph = [[] for _ in range(len(edges)+1)]
        for u, v in edges:
            graph[v].append(u)
            graph[u].append(v)

        indegree = [len(neighbors) for neighbors in graph]
        queue = deque(node for node in range(len(edges)+1) if indegree[node] == 1)
        while queue:
            next_node = queue.popleft()
            for neighbor in graph[next_node]:
                indegree[neighbor] -= 1
                if indegree[neighbor] == 1:
                    queue.append(neighbor)

        for u, v in reversed(edges):
            if indegree[u] == 2 and indegree[v] == 2:
                return [u, v]
```
3. DFS
Time: $O(n)$. Space: $O(n)$
```
class Solution:
    def findRedundantConnection(self, edges: List[List[int]]) -> List[int]:
        
        def find_cycle(node, parent):
            if visited[node] == 1:
                visited[parent] = 2
                cycle_nodes.add(node)
                return
            visited[node] = 1
            for neighbor in graph[node]:
                if neighbor != parent:
                    find_cycle(neighbor, node)
                    if node in cycle_nodes:
                        return
            if visited[node] == 2:
                visited[parent] = 2
                cycle_nodes.add(node)    
            return

        graph = [[] for _ in range(len(edges)+1)]
        for u, v in edges:
            graph[v].append(u)
            graph[u].append(v)

        cycle_nodes, visited = set(), [0] * (len(edges)+1)
        find_cycle(1, 0)
        for u, v in reversed(edges):
            if u in cycle_nodes and v in cycle_nodes:
                return [u, v]
```

['Depth-First Search', 'Topological Sort', 'Python3']