Step-by-step explanation for dummies
Understanding the problem\nProblem statement is to find connections in a graph that, if removed, can result in one or more nodes unreachable. Such connections a
**Understanding the problem**\nProblem statement is to find connections in a graph that, if removed, can result in one or more nodes unreachable. Such connections are called critical connections.\n\nIn other words, a connection is critical when it is a single point of failure: if it is down, there is no other way for the nodes on its two ends to reach each other.\n\nIf a set of nodes in a graph are part of a cycle, then even if one link goes down, the nodes on the two ends of that link will have another way to reach each other.\n\n![image](https://assets.leetcode.com/users/um304/image_1585121353.png)\n\nIn the image above, edges [1, 2], [2, 3], [3, 4], and [4, 1] are not critiacl beacuse all of their connected nodes belong to one cycle. However, edge [0, 1] is critical because it is not part of the cycle.\n\n![image](https://assets.leetcode.com/users/um304/image_1585121732.png)\n\nIn the image above, even though all of the nodes are parts of two different cycles, yet the edge [2, 4] is critical. This is because nodes 2 and 4 belong to two different cycles, and there is no other connection to connect those two cycles (or sub-graphs). Another way to explain this is that if you see the two cycles (or sub-graphs) as nodes (marked by A and B), then those two nodes are not part of a cycle (which would be a cycle of cycles).\n\nSo this reduces the problem to finding out cycles in the graph. Any node that does not fall into a cycle, is part of a critical connection.\n\n**Finding cycles in graphs**\nGraph traversals are very similar to tree traversals. When you\'re traversing a tree with depth-first-search (DFS), there is no way that you\'re going to visit an already visited node again. This is because there is only one path to enter a node.\n\nThis cannot be guaranteed in case of a graph traversal with DFS, because there can be multiple paths to enter one node (which is the reason you have to keep track of visited nodes in graph DFS). So we can say in any connected set of nodes, if there is only one path to enter a node then it is a tree, otherwise it\'s a graph. When there are multiple paths to enter a node, it means there is a cycle in that set of connected nodes. In other words, graphs are trees with cycles. Or, trees are graphs without cycles. \n\nWhen you\'re traversing a graph with DFS, consider as if you\'re doing DFS on a tree. As soon as you find that a child is actually an ancestor of a node (also called a backlink), you\'d know that current node is part of a cycle.\n\n**Trajan\'s algorithm**\nRun a DFS traversal on the graph. As you\'re visiting a node, save the timestamp of your visit with the node. After you have visited all of the nodes, for each node find out (and store as a property of this node) the timestamp of oldest visited node that is reachable from this node (let\'s call this "lowlink", but it can be anything). At the end, you\'d find out that the nodes that belong to same cycle have the same lowlink values. \n\nSince the purpose of timestamp is only to find out the order in which nodes were traversed, you can use a simple integer starting from 0 and increment it every time you visit a new node.\n\n*I\'m skipping directly to solution here because I\'m running out of time. I know there are still a few pieces to explain before moving onto solution.*\n\n**JavaScript Implementation**\n```\nconst buildAdjList = (n, connections) => {\n    const r = Array(n).fill().map(() => []);\n    \n    for (let c of connections) {\n        const [a, b] = c;\n        r[a].push(b);\n        r[b].push(a);\n    }\n    \n    return r;\n}\n\n/**\n * @param {number} n\n * @param {number[][]} connections\n * @return {number[][]}\n */\nvar criticalConnections = function(n, connections) {\n    const adjList = buildAdjList(n, connections);\n    const orderList = Array(n).fill();\n    const lowlinkList = Array(n).fill();\n    \n    let order = 0;\n    const cycles = [];\n    const critical = []\n    \n    const strongConnect = (i, p) => {\n        orderList[i] = order++;\n        lowlinkList[i] = orderList[i];\n        \n        for (const j of adjList[i]) {\n            if (j === p) {\n                continue;\n            }\n            \n            if (orderList[j] === undefined) {\n                strongConnect(j, i);                \n            }\n            \n            lowlinkList[i] = Math.min(lowlinkList[i], lowlinkList[j]);\n            \n\t\t\t// A higher lowlink value for node `j` means that the oldest \n\t\t\t// ancestor that could be reached from node `j` is still younger\n\t\t\t// than node `i`. Had there been any other path from `j` to `i`,\n\t\t\t// `j`\'s lowlink value would have been lower. Hence this connection\n\t\t\t// is critical.\n            if (lowlinkList[j] > orderList[i]) {\n                critical.push([i, j])\n            }\n        }\n        \n    }\n    \n    for (const i in adjList) {\n        if (orderList[+i] !== undefined) {\n            continue;\n        }\n        \n        strongConnect(+i);\n    }\n    \n    return critical;\n};\n```
['JavaScript']