Tarjan Algo | Python | Explanation + Intuition
The basic fundamental of the this approach is based on the time taken to reach one node from the selected root index.  For this question we would select node 1 
**The basic fundamental of the this approach is based on the time taken to reach one node from the selected root index.**  For this question we would select node **1** as the root of the graph.\n\nWe will use two counter **org** and **low**. \n**org[i]** -> would keep track of the actual time needed to reach the i th state from the root\n**low[i]** -> would keep track of the lowest time that would be needed to reach the ith state from the root node.\n\nFor each index we will visited all the children of the node, we will follow the process unless all the nodes have been visited, we will make use of dfs algo, to scan all the nodes and children. For each step we will update the org and low value.\n\nBasic example which would explain how the low value are updated.\n```\n(0,0)  (1,1)  (2,2)  (3,3)  --> The org and the low counter intitally\n1-------2-----3-----4\n|_____________|\n\nNode Connection:\n1->2\n2->3\n3->4\n3->1\n\nIn the above example, there exists a cycle. 1->2->3->1\nTherefore on excuting the algo the low counter for the nodes 1,2,3 would be:\n\nlow[3] = 0, initially the counter was 2 but as there exits one connection to 1, its now 0\nlow[2] = 0, As 2 is conneted to 3 and 3 is connected to 1, the counter for 2 would also become 0\n\n```\n\n**How to determine the bridge / strict connection ?**\n\nThe low counter after scanning all the nodes : \n```\ndefaultdict(<class \'int\'>, {1: 0, 2: 0, 3: 0, 4: 3})\n```\n\nOriginal Counters\n```\ndefaultdict(<class \'int\'>, {1: 0, 2: 1, 3: 2, 4: 3})\n```\n\nIf for any given connection x and y (x-->y) the bridg would be strict if there if the time taken to reach the node y is more than that of node x. \n```\nif low[x] > org[y] or org[x] < low[y], then strict edge\n```\nThis would give edge [3,4] as strict connection \n\n```\nfrom functools import lru_cache\nclass Solution:\n    def criticalConnections(self, n: int, connections: List[List[int]]) -> List[List[int]]:\n        org = collections.defaultdict(int)\n        low = collections.defaultdict(int)\n\n        graph = collections.defaultdict(list)\n        \n        for x,y in connections:\n            graph[x].append(y)\n            graph[y].append(x)\n            \n        visited = set()\n        self.timer = 0\n        @lru_cache(None)\n        def process(node,parent):\n            \n            visited.add(node)\n            \n            org[node] = self.timer\n            low[node] = self.timer\n            self.timer += 1\n\n            for child in graph[node]:\n                if child == parent:continue\n                if child not in visited:\n                    process(child,node)\n\n            for child in graph[node]:\n                if child != parent:\n                    low[node] = min(low[node],low[child])\n\n        process(0,-1)\n        \n        print(low)\n        res = []\n        for x,y in connections:\n            if low[x] > org[y] or  org[x] < low[y]:\n                res.append([x,y])\n                print(x,y)\n        return res\n
['Python3']