ICU For Struggling People Like Me - Java Tarjan based solution
This problem is really hard to me even if I\'ve read the Tarjan algorithm wikipedia and solutions from others. Everytime I run into this kind of problems on lee
This problem is really hard to me even if I\'ve read the Tarjan algorithm wikipedia and solutions from others. Everytime I run into this kind of problems on leetcode, It makes me think whether I have the talent for this profession and whther I\'m qualified to keep being a software engineer. \n\nLuckily, I\'m still here because I know the amount of effort that I put into this area is far from enough. Complaining lack of talent is just an excuse.\n\nI\'ll post my understanding in a verbose way below and hopefully, it can help you a little bit.\n\nThe example in the problem description is like this ![image](https://assets.leetcode.com/uploads/2019/09/03/1537_ex1_2.png) which might misleads you to think a critical connection must be an edge that just connects to a single vertex. However, the graph can be like the shape of a dumbbell too. I\'ll use the graph below as my example\n\n![image](https://assets.leetcode.com/users/shuatify/image_1576362946.png)\n\nApparently, edge `(2,3)` is the only critical connection is this graph and I\'m going to show you how to find it programmatically.\n\nLet me first come up with adjacency list for your convenience.\n\n```\n0 -> [1, 2]\n1 -> [0, 2]\n2 -> [0, 1, 3]\n3 -> [2, 4, 5]\n4 -> [3, 5]\n5 -> [3, 4]\n```\n\nThe reason that we, humanbeings,  can recognize edge `(2,3)` as a critical connection is we find out that without this edge, vertex 3, 4 and 5 can\'t connect to any of vertex 0, 1 and 2 anymore and vice versa. \n\nSo, imagine that when we reach to vertex `A` and see an edge `(A, B)`,  if vertex `B` and any vertexes that conect to `B` (except vertex `A`) have no route to connec to vertex `A` and any vertexes that connect to `A`, then edge `(A, B)` is the critical connection we\'re looking for.\n\nSince we\'ll traverse vertexes based on chronological order, each vertex will have a timestamp (you can call it rank, discovered order or whatever that helps you understand) to mark the moment we reach to it. \n\nBecause each vertex has at least one edge connects to it, therefore, when we reach to the `currentVertex` through an edge, we must have visited the `previousVertex` except that the scenario that the `currentVertex` is the first vertex  we start with. So, we assume we have visited some dummy vertex (use non-existing vertex id, e.g. -1 as the vertex id) before we reach to the first vertex that we actually visit.\n\nAssume we have visited a bunch of vertexes and then we visited vertex `A` and finally reaches to vertex `B` through edge `(A, B)`, if vertex `B` has other edge that can connect to vertexes that we have visited (except vertex `A`) then it\'s like vertex `B` has a time tunnel that can travel back to history. As a result of the existence of the "time tunnel" and edge `(A, B)`, neither the "time tunnel" nor edge `(A, B)` is critical connection anymore. Like the graph below, if we traverse from left to right and with the existence of the orange dashed line as the "time tunnel", the privious critical connection is not valid anymore.\n\n![image](https://assets.leetcode.com/users/shuatify/image_1576366350.png)\n\nEssentially, the "backward time travel" capability will help us identify critical connection. we use the an array `lowLink[]` to track the earliest moment that each vertex can travel back. `lowLink[i]` means the earliest moment that vertex`i` can travel back to. Obviously, the initial value of `lowLink[i]` is the timestamp that we reach to them. \n\nTalk is cheap, it\'s time to show you the code\n\n```\nclass Solution {\n    public List<List<Integer>> criticalConnections(int n, List<List<Integer>> connections) {\n        List<List<Integer>> result = new LinkedList<>();\n        \n\t\t// build adjacency list, boilerplate code for graph problems\n        List<Integer>[] graph = new LinkedList[n];\n        for(int i = 0; i < n; i++) {\n            graph[i] = new LinkedList<>();\n        }\n        \n        for(List<Integer> connection : connections) {\n            int vertex1 = connection.get(0);\n            int vertex2 = connection.get(1);\n            graph[vertex1].add(vertex2);\n            graph[vertex2].add(vertex1);\n        }\n        \n\t\t\n        boolean[] visited = new boolean[n];   // flag to show if we\'re reached a vertex or not\n        int[] lowLink = new int[n];    // the earliest moment that vertexes can travel back to\n        \n        dfs(graph, visited, lowLink, result, 0, -1, 0);\n        return result;\n    }\n    \n    private void dfs(List<Integer>[] graph, boolean[] visited, int[] lowLink, List<List<Integer>> result, int timeStamp, int previousVertex, int currentVertex) {\n        visited[currentVertex] = true;    // now, we have visited the "currentVertex"\n        lowLink[currentVertex] = timeStamp;    // record the time timestamp that we visit the "currentVertex"\n        \n\t\t// iterate over vertexes that in the edges that starts with "currentVertex"\n        for(int nextVertex : graph[currentVertex]) {\n\t\t    // we walk along edge (previousVertex, currentVertex) to reach "currentVertex"\n\t\t\t// so we don\'t want to repeat\n            if(nextVertex == previousVertex) continue;\n            \n            if(!visited[nextVertex]) {\n                dfs(graph, visited, lowLink, result, timeStamp+1, currentVertex, nextVertex);\n            }\n\t\t\t\n\t\t\t// since (currentVertex, nextVertex) is an edge, "currentVertex" can travel back to\n\t\t\t// any earlier moment that nextVertex can travel to\n            lowLink[currentVertex] = Math.min(lowLink[currentVertex], lowLink[nextVertex]);\n\n\t\t\t// walk along edge (currentVertex, nextVertex) will arrive at "nextVertex" at the moment timeStamp+1\n\t\t\t// so if "nextVertex" has no chance to travel to any moment that is earlier than timeStamp+1\n\t\t\t// then edge (currentVertex, nextVertex) is a critical connection\n            if(lowLink[nextVertex] >= timeStamp + 1) {\n                result.add(Arrays.asList(currentVertex, nextVertex));\n            }\n        }\n    }\n}\n```\n\nHopefully, the code with explaination above could help you understand this problem.\n\nThe `visited[]` array is to make things clear but it isn\'t necessary as we can initialize `lowLink[]` array with all `-1`s to indicate that a vertex hasn\'t been visited yet. \n\n\n\n\n\n\n\n\n
[]