[Python] No "Tarjan" stuff. My own solution and thoughts
OK, this title might be a little bit exaggerated. This algorithm may actually be similar to Tarjan\'s, but I came up with it myself and didn\'t Google it. I jus
OK, this title might be a little bit exaggerated. This algorithm may actually be similar to Tarjan\'s, but I came up with it myself and didn\'t Google it. I just hate it when the solution to an interesting problem is some obscure academic algorithm that nobody knows except Gennady Korotkevich and Jesus himself (arguably the same person).\n\nThis algorithm basically does the following:\n- Consider a path of nodes, n1 -> n2 -> ... -> nM -> i, that ends at node `i`.\n\t- Try to find a path from i to one of the previous path nodes, nX such that:\n\t\t- The path does not include i -> nM.\n\t\t- The X such that there\'s a path from i -> nX is minimized. In other words, the node we find is as early on in the path we\'ve created as possible.\n\t- Once we have the earliest nX possible, we can set all edges in the path nX -> n(X+1) -> ... -> i to be non-critical. \n\t\t- Why? Because all of these nodes form a cycle, so they\'re all reachable from one another regardless of whether one of them gets erased.\n\nThe challenge is doing it in an efficient way that doesn\'t require visiting each node more than once, so here\'s my solution. **I might recommend copying the code into your own IDE and removing the comments if you think you understand the explanation, as they might make the code hard to read.**\n\n```\n# Time complexity: O(V + E) because we only visit each node (and therefore, each edge) once.\nclass Solution:\n    def criticalConnections(self, n: int, connections: List[List[int]]) -> List[List[int]]:\n        # m is an adjacency list for the graph\n        m = [set() for _ in range(n)]\n        for i, j in connections:\n            m[i].add(j)\n            m[j].add(i)\n            \n        # s will keep track of the connections that are still potentially critical\n        # we\'ll remove elements from this set as we get more information about the graph,\n        # and whatever\'s left after we\'re done is what\'s critical.\n        s = set(tuple(el) for el in connections)\n        # seen tells us the position of the node in the current path of nodes\n        # we\'ve visited in O(1) time. a stack isn\'t necessary, but this basically simulates one\n        # so for a path 0 -> 2 -> 1, seen = {0: 0, 2: 1, 1: 2}\n        seen = {}\n        # settled is a hash set of nodes we\'ve already seen, and therefore no longer need to visit\n        settled = set()\n        \n        # our depth-first-search function returns a number. This number represents how far back\n        # we\'ve found a cycle after traversing the edge from "last" to "i." It\'s infinity if \n        # there is no cycle at all.\n        def dfs(i = 0, last = None):\n            if i in seen:\n                # if i is in the hash map representing our state, "seen," then we\'ve found a cycle.\n                # how big the cycle is depends on how far back this element is; that\'s why we need\n                # "seen" to be a hash map and not a hash set. If i is at position x for some path\n                # of nodes of length N where x < N, then we need to mark *at least* the last (N - x - 1) \n                # edges in this cycle as non-critical, because we don\'t need them to keep the graph connected.\n                return seen[i]\n            elif i in settled:\n                # we don\'t need to visit a node twice because we already know we\'ve handled its cycles.\n                # so, if we revisit one, just treat this node as if it doesn\'t have any cycles\n                return float(\'inf\')\n            else:\n                # i is a new node, so add it to our path of nodes of length N at position N; \n                seen[i] = len(seen)\n                # now our path of nodes is length N + 1\n\n                # we want to learn two things using the information we get from each neighbor:\n                # 1. how many of this node\'s edges are non-critical and need to be removed?\n                # 2. how *far back* do we have to go in this node\'s path before we find\n                #    edges that may be critical?\n                ret = float(\'inf\')\n                for j in m[i]:\n                    # don\'t revisit the last node\n                    if j != last:\n                        res = dfs(j, i)\n                        # its possible that whatever non-critical node this neighbor\'s logic identified\n                        # isn\'t actually in the path anymore. if so, treat it like it\'s float(\'inf\')\n                        if res < len(seen):\n                            # we\'re going to return "ret" in the end to tell our previous nodes in the\n                            # path which edges are not critical. if we find more than one cycle, we want\n                            # to tell the previous nodes about the cycle that connects to the earliest \n                            # possible node in the path, so take the min.\n                            # for example, consider the path 0 -> 1 -> 2 -> 3\n                            # if 3 is connected to both 0 and 2, which one\'s position do we want to return\n                            # from this function? the answer is 0\'s position, because if 3 -> 0, then\n                            # all of the edges in this path after 0 are non-critical. if 3 -> 0, then\n                            # it doesn\'t matter if 3 is connected to 1 or 2 directly or indirectly,\n                            # so return the earliest one\n                            ret = min(ret, res)\n                            \n                            # remove the node from our critical set\n                            for t in ((i, j), (j, i)):\n                                if t in s:\n                                    s.remove(t)\n                                    \n                del seen[i]\n                \n                settled.add(i)\n                return ret\n                \n        dfs()\n        return list(list(el) for el in s)\n```\n\nPlease ask any questions in the comments. I\'d appreciate an upvote if you found this helpful!
['Depth-First Search', 'Python']