[Python] Two DFS approaches with detailed explanation
Approach -1- Brute Force [34/39]\nO(E) * O(E+V)\n\nMy Approach\n- Iterate over the edges of the graph and remove an edge one at a time\n- for each edge that is 
**Approach -1- Brute Force [34/39]**\n**O(E) * O(E+V)**\n\n**My Approach**\n- Iterate over the edges of the graph and remove an edge one at a time\n- for each edge that is removed:\n            - check if the resulting graph is a tree\n            - (problem magically transfomred into (isGraphValidTree)\n            - we know 3 properties of a tree:\n                1 - Acyclic\n                2 - connected\n                3 - nodes = edges + 1\n            \n\t- Howeverbecause we know an edge was inserted between two different, already-exiting nodes,\n\t\twe know for fact that porperties (2 and 3) are true which only leaves property 1 (detec a cycle)\n\t\tThe problem has been simplified even further to (detec a cycle in an undirected graph)\n\t\t\t\t\n**Code**\n\n```\ndef findRedundantConnection(self, edges: List[List[int]]) -> List[int]:\n    \n        # helper - hasCycle - #\n        def hasCycle(node):\n            \'\'\'DFS - detec cycle in undirected graph using visited set\'\'\'\n            stack = [node]\n            visited = set()\n            while stack:\n                node = stack.pop()\n                for n in treeDict[node]:\n                    if n not in visited:\n                        stack.append(n)\n                        visited.add(n)\n                        treeDict[n].remove(node)\n                    else: # n is in visit -> cycel\n                        return True\n                del treeDict[node]\n            return False\n            \n        # main function #\n        # 1 - convert edges to adjlist dict:\n        from collections import defaultdict\n        d = defaultdict(list)\n        for edge in edges:\n            k, v = edge\n            d[k].append(v)\n            d[v].append(k) # undirected\n            \n        for i in reversed(range(len(edges))): # reversed becuz we are told to give priority to edges near the end\n            # copies:\n            candidateTree = copy.deepcopy(edges)\n            treeDict = copy.deepcopy(d)\n            # mutate edges (edge list)\n            candidateTree.pop(i)\n            # mutate (adj list) dict - remove symmetric edge:\n            treeDict[edges[i][0]].remove(edges[i][1])\n            treeDict[edges[i][1]].remove(edges[i][0])\n            \n            # now check if candidateTree is acyclic\n            startNode = candidateTree[0][0] # random choice\n            if not hasCycle(startNode):\n                print(edges[i])\n                return edges[i]\n        return [0]\n        \n            \n```\n\n**THE REASON WHY MY APPROACH WON\'T GENERALIZE WELL**\n- Consider the following test-case:\n\n-![image](https://assets.leetcode.com/users/abadawi/image_1565275832.png)\n- By removing the intermediate edge shown in the sketch, we get a disjoint graph. This can be specially problematic if one part (connected component)(for example part A) of the graph is a tree while the other part (part B) is a graph. \n- So even if you iterate over the nodes, you might find yourself applying DFS on part(A) which will obviosuly return (no cycle found) and thus the algorithm will return the removed edge as the desired edge while in fact it didn\'t successfuly convert the input graph into a tree (but instead converted only a portion of it to a tree).\n\n![image](https://assets.leetcode.com/users/abadawi/image_1565270721.png)\n\n![image](https://assets.leetcode.com/users/abadawi/image_1565271004.png)\n\n\n**Approach -2- Intutive**\n**time: O(E) * O(E+V)**\n\n- iterate over edges -> add one edge at a time to graph\n- for the edge at hand, check if:\n\t\t1- the two nodes represented by the edge already exit in the graph\n\t\t2- the above mentioned nodes are already connected undirectly (via a longer route)\n\t- if 1 & 2 -> then edge at hand (the one you\'re about to insert into the graph) is \n\tredundant. Mark it as such and proceed to add it to graph\n\n\n```\n# - helper - #\ndef dfs(k, v):\n\tstack = [k] # start at k and see if you can reach v\n\tvisited = set()\n\twhile stack:\n\t\tnode = stack.pop()\n\t\tif node == v:\n\t\t\treturn True\n\t\tvisited.add(node)\n\n\t\tfor nei in d[node]:\n\t\t\tif nei not in visited:\n\t\t\t\tstack.append(nei)\n\treturn False\n\n\n# - main logic - #\nif not edges:\n\treturn []\n\nfrom collections import defaultdict\nd = defaultdict(list)\n\nredundant = []\nfor k, v in edges:\n\t# 1 - check if nodes exist already\n\tif k in d and v in d:\n\t\t# 2 - check if k and v are connected:\n\t\tif dfs(k, v):\n\t\t\tredundant.append(k)\n\t\t\tredundant.append(v)\n\n\n\td[k].append(v)\n\td[v].append(k) # undirected\n\nreturn redundant\n```\n
['Depth-First Search', 'Python']