Optimal C++ solution with best explanation || Tarjan's Algorithm
If you find this helpful, please consider upvoting!\n# Code\n\nclass Solution\n{\nprivate:\n    void DFS_TarjansAlgo(int node,int parent,vector<bool>& visited,v
> If you find this helpful, please consider upvoting!\n# Code\n```\nclass Solution\n{\nprivate:\n    void DFS_TarjansAlgo(int node,int parent,vector<bool>& visited,vector<int> adj[],vector<int>& insertionTime,vector<int>& lowestTime,vector<vector<int>>& ans,int &timer)\n    {\n        visited[node] = true;\n        // initially insertion/discovery time & the lowest time for the node will be equal to timer only\n        insertionTime[node] = lowestTime[node] = timer;\n        timer++;\n        for(auto nbr:adj[node])\n        {\n            if(nbr == parent) continue;\n\n            if(!visited[nbr])\n            {\n                DFS_TarjansAlgo(nbr,node,visited,adj,insertionTime,lowestTime,ans,timer);\n                // after the end of the DFS call for the nbr \n                lowestTime[node] = min(lowestTime[node],lowestTime[nbr]);\n                // 2nd thing is we need to check that this edge is a bridge edge or not\n                if(lowestTime[nbr] > insertionTime[node])\n                {\n                    ans.push_back({node,nbr});\n                }\n            }\n            else\n            {\n                lowestTime[node] = min(lowestTime[node],lowestTime[nbr]);\n            }\n        }\n        \n    }\n\npublic:\n    vector<vector<int>> criticalConnections(int n, vector<vector<int>>& connections)\n    {\n        // here after reading the problem statement we can clearly observe that ve need to find the bridges not the bridges count but the edge of bridge\n        // here we have edges we need to create adjacency list from it\n        vector<int> adj[n];\n        for(auto edge:connections)\n        {\n            int u = edge[0];\n            int v = edge[1];\n\n            adj[u].push_back(v);\n            adj[v].push_back(u);\n        }\n        // --------------------------- STEP 1: Initial Requirements\n\n        // we need a insertion time array or we can say discovery time array\n        vector<int> insertionTime(n,-1);\n        // we need a lowest time array in which we can reach array that node\n        vector<int> lowestTime(n,-1);\n        // we also need a visited array to keep track which node is already visited\n        vector<bool> visited(n,false);\n        // we need an answer to return \n        vector<vector<int>> ans;\n        // we need a timer also \n        // initially we are taking timer as 1 i.e. first DFS for node 0 will be called at time 1\n        int timer = 1;\n\n        // ---------------------------- STEP 2: Perform DFS & while returning check if parents lowest time is getting updated or not by child & then check if that node can be a bridge node or not \n        // an bridge condition will be :\n        // if(low[nbr] > insertionTime[node]) i.e. if connection broken nbr cant reach node so this is a bridge conditon and push this in the answer\n\n        // here all are connected components so we do not need to worry about more than one components of the Graph so we will once call DFS for the source node it will visit whole Graph\n        DFS_TarjansAlgo(0,-1,visited,adj,insertionTime,lowestTime,ans,timer);\n\n        return ans;\n    }\n};\n```
['Backtracking', 'Depth-First Search', 'Graph', 'Biconnected Component', 'C++']