Python3 | DFS | with clear explanation
Intuition\nRedundant edge will always be the one which is responsible for forming a cycle within graph. And we can be ensured that a cycle will be formed becaus
# Intuition\nRedundant edge will always be the one which is responsible for forming a cycle within graph. And we can be ensured that a cycle will be formed because number of edges >= number of nodes. \n\n\nLet\'s consider the input -\n[[1,2],[1,3],[2,3]]\n\nLet\'s form the graph - \n![redundant_conn.png](https://assets.leetcode.com/users/images/41d90a50-e0e9-420c-9508-07ff0c0a4f86_1691410730.8587778.png)\n\n# Pseudo Code\n1. keep track of graph constructed so far\n2. for each pair of nodes (u,v) provided in input\n   - check if path exists between u and v using dfs\n   - if it exists it means that adding the current edge will create a cycle hence return (u,v) as answer\n   - else add that to graph\n\n# Complexity\n- Time complexity:\n$$O(n^2)$$ because for each pair of nodes we run dfs.\n=> $$O(n)$$ during **for loop** and $$O(n)$$ during **dfs** \n\n- Space complexity:\n$$O(n)$$\n\n# Code\n```\ndef findRedundantConnection(self, edges: List[List[int]]) -> List[int]:\n    # variable to keep track of graph constructed so far\n    graph_so_far = collections.defaultdict(lambda: [])\n    \n    # dfs function to check if path exists between nodes u and v\n    def path_exists(u, v):\n        # we reached to v from u\n        if u == v:\n            return True\n\n        # mark u as visited\n        visited.add(u)\n\n        # iterate through all the neighbors of u and if they are not visited call dfs on them\n        for neighbor in graph_so_far[u]:\n            if neighbor not in visited:\n                if path_exists(neighbor, v):\n                    return True\n                    \n        return False\n\n    # iterate through all the pairs of edges\n    for u, v in edges:\n        # we make a fresh visited because we call dfs for every pair of edges\n        visited = set()\n        # if path exists between u and v return that\'s the answer\n        if path_exists(u,v):\n            return [u,v]\n        else:\n            # if path does not exist we add edges to graph\n            graph_so_far[u].append(v)\n            graph_so_far[v].append(u)\n\n    return None\n```
['Depth-First Search', 'Python3']