Java Solution With Detailed Explanation and Comments
For this question, we need to find out all critical connections. In other words, we need to find out all edges that in a circle in this graph. After removing th
For this question, we need to find out all critical connections. In other words, we need to find out all edges that in a circle in this graph. After removing those edges in a circle, the rest of them are critical connections.\n\nFirst, we can create a graph. We dfs this graph from a starting point. \n\nIf we run into a circle, we know those edges in this circle are not critical connections.\n\nAs there\'s a posibility to enter into a circle, we need a `visited` map to help us track if we visited this node already; otherwise, our dfs would run infinitely.\n\nWhile we dfs each node, we need a integer, `timer`, to help us track how long we\'ve been through this dfs.\n\nWith this `timer`, when we dfs to a previous visited node and find the circle, we can use the lower `timer` to update the current node. And use the lowest `timer` to update each node\'s timestamp in this circle while we backtrack from the dfs. \n\nIn this way, each circle in the graph will have a idential `timer` for themselves. \n\nFor example, if we have 10 nodes, and there are 3 circles totally. We start DFS from one of the nodes, and update `timer` of each node. \n\nAll nodes on the 1st circle may have the same `timer`: 1, all nodes on the 2nd circle may have the same `timer`: 3, and all nodes on the 3rd circle may have the same `timer`: 5\n\nAfter doing all those things, we would know if two nodes have the same `timer`, the edge between them is not critical connection; otherwise, it\'s a critical connection. \n\nMy sample java code is below:\n-----------------------------------------------------------------------------------\n\n```   \nclass Solution {\n\t// We define some variables here, so we don\'t have to bother passing them between recursions\n\n\t// We need a graph to store each node and store the connection info between each node\n\t// As all nodes are marked from 0 ~ n-1, we can use array to store each node,\n\t// and a list to store the connection info\n\tList<Integer>[] graph;\n\t// We need a visited map to record if we visite a node already\n\tboolean[] visited;\n\t// We need a timestamp map to record timer info of each node\n\tint[] timestamp;\n\t// We need a global integer to represent the timer\n\tint timer;\n\t// We need a variable to store the ans\n\tList<List<Integer>> ans;\n\t\n\tpublic List<List<Integer>> criticalConnections(int n, List<List<Integer>> connections) {\n\t\t// Start building the graph\n\t\tgraph = new ArrayList[n];\n\t\tfor(int i = 0; i < n; i++) graph[i] = new ArrayList<>();\n\t\tfor(List<Integer> each : connections) {\n\t\t\tgraph[each.get(0)].add(each.get(1));\n\t\t\tgraph[each.get(1)].add(each.get(0));\n\t\t}\n\t\t// Initialize those global variables\n\t\tvisited = new boolean[n];\n\t\ttimestamp = new int[n];\n\t\ttimer = 0;\n\t\tans = new ArrayList<>();\n\t\t// Start the dfs from node 0, and no prev node so far\n\t\tdfs(-1, 0);\n\t\t// As this is a connected graph, dfs will make sure we visited each node and collect all critical connections\n\t\treturn ans;\n\t}\n\t\n\tpublic void dfs(int prev, int curr) {\n\t\t// Mark the curr node as visited\n\t\tvisited[curr] = true;\n\t\t// Record the current timestamp for this node\n\t\ttimestamp[curr] = timer;\n\t\t// Use a local variable to store the current time as the actual timestamp for the later comparison usage\n\t\t// Because each node\'s timestamp might be updated later during the dfs\n\t\tint currTime = timer;\n\t\t// After recording, increase the timer as we will move to next node later\n\t\ttimer++;\n\t\t\n\t\t// Start dfs each connected node of the current node\n\t\tfor(int other : graph[node]) {\n\t\t\t// Skip if the connected node is the previous node.\n\t\t\tif(other == prev) continue;\n\t\t\t// Dfs this node if we haven\'t visited it yet\n\t\t\tif(!visited[other]) dfs(node, other);\n\t\t\t// If after doing the dfs call or not doing it, we find the other node has a lower timer.\n\t\t\t// We could tell the other node mighe be a previous visited node or it\'s a node in the circle that has been updated\n\t\t\t// to the lowest timer in that circle.\n\t\t\t// In other words, the current node is in that circle as well. So we update the current node to the lowest timer in\n\t\t\t// that circle.\n\t\t\ttimestamp[node] = Math.min(timestamp[node], timestamp[other]);\n\t\t\t// If we are not in a circle, the previous line won\'t take effect. That means\n\t\t\t// the other node\'s timer is higher than the current one. \n\t\t\t// Which must be higher than, because we visited the other node later than the current one\n\t\t\t// It proves the other node mighe be in another circle or just by itself. \n\t\t\t// So we can say the edge between current node and the other node is critical connection\n\t\t\tif(currTime < timestamp[other]) ans.add(Arrays.asList(node, other));\n\t\t}\n\t}\n}\n```
[]