Python 52ms DFS Algorithm with Explanations (compared with 52ms union-find)
The algorithm based on the following fact in graph theory:\n\na simple connected graph with no cycle is a tree.\n\nThe statement of the problem guarantees that 
The algorithm based on the following fact in graph theory:\n\n**a simple connected graph with no cycle is a tree**.\n\nThe statement of the problem guarantees that by deleting one and only one edge the graph is a tree, so we know it is connected and has one cycle. Our goal is to find the edge in this cycle with the largest index and return it.\n\nHow? DFS!\n\nWe store the graph in a dictionary `e` so that we can easily find adjacent vertices. `indices` helps me keep track of the original indices of edges in `edges`. `path` is to record the fact that we arrive at a vertex `v` from `path[v]`.\n\nWhen constructing `e`, we already get rid of the 2-cycle case by\n```\n            if p[1] in e[p[0]]:\n                return p\n```\nso in DFS, we only focus on cycles whose length >= 3. Since the graph is connected, we will find the cycle wherever we start. Pick one randomly (i.e., `e.keys()[0]`) and set off!\n\nIn `DFS(v)`: \n1) Look at all vertices 'w' adjacent to v such that the predecessor of `v` in DFS path is not `w` (otherwise it would be a two-vertex infinite loop, and we know there is no 2-cycle).\n\n2) If `path[w] != 0`, means `w` is on the current DFS path! The cycle is found and just need to make the change `path[w] = v` to complete the cycle and return the result.\n\n3) Standard DFS things: we record down the path in `path` and after DFS change it back to 0 state.\n\n4) It is possible that the DFS path goes into a dead end, so in a branch of DFS, it is possible that nothing is returned. We respect this possibility and do the check\n```\n                temp = DFS(w)\n                if temp:\n                    return temp\n```\nThe function `Result` is just a practice of typing once we have `indices` which indicates the corresponding indices for edges.\n\nMy thought is pretty natural besides the fact that for this problem union-find is a method much easier to type up (and could be as fast). Anyway, here is my DFS algorithm:\n\n```\n        def Result(w):  # given w is a vertex in a cycle, find the edge with the largest index in this cycle\n            prev, curr =w, path[w]\n            M = indices[(curr, prev)]\n            while curr != w:\n                prev, curr = curr, path[curr]\n                M = max(M,indices[(curr, prev)])\n\n            return edges[M]\n        \n        def DFS(v):\n            for w in e[v]:\n                if path[v] == w:  # if predecessor of v is w, it's bad\n                    continue\n\n                if path[w] != 0:  # the cycle is found\n                    path[w] = v   # complete the cycle\n                    return Result(w)\n\n                path[w] = v\n                temp = DFS(w)\n                if temp:          # in case it is a dead end and returns nothing\n                    return temp\n                path[w] = 0\n        \n        e = collections.defaultdict(set)  # e[x] is the set of all vertices adjacent to x\n        indices = {}                      # key is edge, value is indices in the list 'edges'\n        for i,p in enumerate(edges):\n            if p[1] in e[p[0]]:\n                return p                  # if one edge appears twice in 'edges', return tha latter one\n            e[p[0]].add(p[1])\n            e[p[1]].add(p[0])\n            indices[(p[0],p[1])] = indices[(p[1],p[0])] = i\n\n        path = {x:0 for x in e}           # record the path in DFS\n        return DFS(e.keys()[0])\n```\nMy union-find algorithm with best time performance:\n```\n        def find(v):                         # find the root of the tree\n            return find(parent[v]) if v in parent else v\n\n        parent = {}                          # record the child: parent relation in the forest\n        for i,p in enumerate(edges):\n            r1, r2 = map(find, p)\n            if r1 == r2:\n                return p\n            else:\n                parent[r1] = parent[r2] = str(i) # use str(i) as the tree label\n```
['Depth-First Search', 'Union Find', 'Python']