Python: Easy to understand: GRAPH - DFS
As we read the question, it is clearly a Graph related question that emphasizes on finding a cycle in the graph. \n\nIt differs from other graph-cycle finding p
As we read the question, it is clearly a Graph related question that emphasizes on finding a cycle in the graph. \n\nIt differs from other graph-cycle finding problem in a way that, in general graph cycle finding problem we just need to say that whether a cycle exists or not. But in this problem we need to **return the edge that caused the cycle** and if multiple edges caused the cycle then we need to return the later occuring edge.\n\n**Note:** *The question says the edge was added later, and did not exist earlier. So, in my view, we should keep developing the graph by adding edges one by one and performing cycle check simultanesouly.*\n\n***Cycle Check can be performed using a standard DFS algorithm using visited sets.***\n\nThe basic flow of code:\n```\n\t\tn = len(edges)  # the number of nodes == number of edges, in this question (Given) \n        \n\t\t"""\n\t\tThe graph for [[2,1],[1,3],[2,3]] will look like:\n\t\t\tgraph [1] = [2,3]\n\t\t\tgraph [2] = [1,3]\n\t\t\tgraph [3] = [1,2]\n\t\tAs the graph is undirected.\n\t\t\n\t\t"""\n\t\t\n\t\tgraph = defaultdict(list) \n        \n        ans = []\n\t\t# for each edge in edges\n        for u, v in edges:\n            visited = set()\n\t\t\t# perform dfs every time you add an edge\n\t\t\t# so that we if a cycle is formed we know exactly this edge has caused the cycle\n            if dfs(u, v):\n\t\t\t\t# do not return the edge directly here\n\t\t\t\t# as we want the last possible edge that caused the cycle\n                ans = [u,v]\n\t\t\t# add the edge and reverse edge in graph as it is undirected\n            graph[u].append(v)\n            graph[v].append(u)\n        return ans\n```\n\nNow the simple Cycle Detection Algorithm using DFS:\nIdea: If u, v is already an edge and through DFS we found v can be reached from u, then a cycle exists. We can say that DFS will find a different path because, we have not yet added [u,v] in the graph. Only after we return from DFS we add it to graph.\n\n```\n\t\tdef dfs(u,v):\n\t\t\t# if a node is visited we cannot find a path through it as it itself formed a cycle which we do not want\n            if u in visited:\n                return False\n\t\t\t# if dfs finally reached to the node \'v\' means it has found path from \'u\' to \'v\'.\n            if u == v:\n                return True\n            \n\t\t\t# mark the node of dfs as visited.\n            visited.add(u)\n            \n\t\t\t# each node connected to u, split the different dfs recurssion path\n            for i in graph[u]:\n                if dfs(i, v):\n                    return True\n            return False\n```\n\nI hope this made it clear!\n\nTime = O(n) for DFS and O(n) for preparing the graph simultanesouly = O(n^2).\nSpace = O(n) for recurssion stack.\n\n**The FULL CODE:**\n```\nclass Solution:\n    def findRedundantConnection(self, edges: List[List[int]]) -> List[int]:\n        \n        def dfs(u,v):\n            if u in visited:\n                return False\n            if u == v:\n                return True\n            \n            visited.add(u)\n            \n            for i in graph[u]:\n                if dfs(i, v):\n                    return True\n            return False\n        \n        \n        n = len(edges)\n        graph = defaultdict(list)\n        \n        \n        ans = []\n        for u, v in edges:\n            visited = set()\n            if dfs(u, v):\n                ans = [u,v]\n            graph[u].append(v)\n            graph[v].append(u)\n        return ans\n```\n
['Depth-First Search', 'Graph', 'Python']