C++ Tarjan’s Algorithm (DFS) with Visualization
I found this post really helpful to understanding Tarjan\'s Algorithm.\nBasically, it does DFS to keep record of disc and low value for each node.\n- disc: when
I found [this post](https://emre.me/algorithms/tarjans-algorithm/) really helpful to understanding Tarjan\'s Algorithm.\nBasically, it does DFS to keep record of `disc` and `low` value for each node.\n- `disc`: when (or at what level) the node is discovered in DFS\n- `low`: lowest level node reachable from current node\n\nThe following image from [this post](https://emre.me/algorithms/tarjans-algorithm/) illustrate such process. The numbers inside the circle is `disc` and outside is `low` value. \nThe way to determine a critical connection is whether the `disc` value of the edge coming from is smaller than the `low` value this edge is going to.\n\nOnce we understand how a critical bridge is determined, the solution is nothing but a DFS.\n![image](https://assets.leetcode.com/users/images/c18812ff-46e8-438e-9294-e7f9cc6e3b73_1597797545.932957.png)\n\nHere is the C++ solution:\n```cpp\nclass Solution {\npublic:\n    vector<vector<int>> criticalConnections(int n, vector<vector<int>>& connections) {\n        // Build graph\n        vector<vector<int>> g(n);\n        for (auto& conn : connections) {\n            g[conn[0]].push_back(conn[1]);\n            g[conn[1]].push_back(conn[0]);\n        }\n        \n        vector<vector<int>> bridges;\n        vector<int> disc(n, -1), low(n, -1);\n        \n        std::function<void (int, int, int)> dfs = [&](int node, int parent, int level) {\n            if (disc[node] >= 0) return;  // visited\n\n            disc[node] = low[node] = level;\n            for (auto& nei : g[node]) {\n                if (nei == parent) continue;\n\n                // neighbor has not been discovered\n                if (disc[nei] < 0) {\n                    dfs(nei, node, level + 1);\n\n                    low[node] = min(low[node], low[nei]);\n                    if (disc[node] < low[nei]) bridges.push_back({node, nei});\n                } else {\n                    low[node] = min(low[node], disc[nei]);\n                }\n            }\n        };\n        \n        dfs(0, -1, 0);\n        return bridges;\n    }\n};\n```\n\nArticles:\n- https://emre.me/algorithms/tarjans-algorithm/\n- https://www.hackerearth.com/practice/notes/nj/\n
['C']