Python DFS with explanation
Solution explanation is pretty vague, I think this is a better explanation for the DFS solution. \n\nclass Solution:\n    \'\'\'\n    Tree Properties\n    1) On
Solution explanation is pretty vague, I think this is a better explanation for the DFS solution. \n```\nclass Solution:\n    \'\'\'\n    Tree Properties\n    1) Only 1 edge between two vertices\n    2) Every child can have only one parent\n    3) No cycles\n    4) Must have n-1 edges where n is the number of vertices     \n    \n    In a valid tree, there is a unique path from each node to every other\n    node in the tree:\n    \n         1                  1 -> 2: (1,2)\n        / \\                 1 -> 3: (1,3)\n       2   3                2 -> 3: (2,1,3)\n                            3 -> 2: (3,1,2)\n\n    If we add one more edge to this tree, then the tree would be invalid:\n    \n         1                  1 -> 2: (1,2),   (1,3,2)\n        / \\                 1 -> 3: (1,3),   (1,2,3)\n       2 - 3                2 -> 3: (2,1,3), (2,3)\n                            3 -> 2: (3,1,2), (3,2)\n    \n    To find the redundant connection we can iterate through the list of edges\n    and create the graph as we go along the list. For each node u,v in the list\n    of edges if both u and v exist as nodes in the graph, then we can try and \n    form a path from u to v. \n    \n    If the u -> v path already exists then adding another edge from u to v would \n    make our tree invalid.\n    \'\'\'    \n    def dfs(self, graph, src, dest, visited):\n        if src not in visited:\n            visited.add(src)\n            neighbors = graph[src]\n            \n            # We have found a path from src to dest\n            if src == dest:\n                return True\n            \n            for neighbor in neighbors:\n                path = self.dfs(graph, neighbor, dest, visited)\n                if path:\n                    return True\n                \n            # No path from src to dest\n            return False\n                \n    def findRedundantConnection(self, edges: List[List[int]]) -> List[int]:\n        graph = collections.defaultdict(set)\n        \n        for edge in edges:\n            u,v = edge\n            # If we can reach edge u from edge v already then this edge is redundant\n            if u in graph and v in graph and self.dfs(graph, u, v, set()):\n                return edge\n            # No path from u to v, this edge is valid\n            graph[u].add(v)\n            graph[v].add(u)\n            \n        return graph\n```
[]