Explained | Beats 86% of the solution | Tarjan's Algorithm | T.C. O(E + V) | S.C O(V + 2E + 3N)
Intuition\nEach node will check for its adjacent that if the adjacent is accesible after removing the exsiting edge.\n\n# Approach\nTwo vectors named low(repres
# Intuition\nEach node will check for its adjacent that if the adjacent is accesible after removing the exsiting edge.\n\n# Approach\nTwo vectors named low(represent the lowest time of insertion it can access except its parent) and tin(represent the time of insertion of current node).\n\nWe do DFS traversel on the graph. If adjacent node is not visited then call DFS traversal.\nThe DFS traversal will mark if as visited and set value of tin and low.\nWhen the DFS call for the adjacent node is completed then node will check for the min val of low[node] and low[adjacent node] and then it will check if adjacent node can be visited after removing the edges(this can be checked by the condition if(tin[node] > low[adjacent node]) , if this condition is true then it means that the adjacent node cannot be visited after removal of the edges). Therefore this edge will be a part of answer.\n\n\n# Complexity\n- Time complexity:\nO(E + V)\n\n- Space complexity:\nO(V + 2E + 3N)\n\n# Code\n```\nclass Solution {\n    int timer = 1;\npublic:\nvoid dfs(vector<int>adj[] , int node , int parent , vector<int>&tin , vector<int>&low , vector<int>&vis , vector<vector<int>>&ans)\n{\n    vis[node] = 1;\n    tin[node] = low[node] = timer;\n    timer++;\n    for(auto it:adj[node])\n    {\n        if(it == parent) continue;\n        if(vis[it] == 0)\n        {\n            dfs(adj , it , node , tin , low , vis , ans);\n            low[node] = min(low[node] , low[it]);\n            if(tin[node] < low[it])\n            ans.push_back({node , it});\n        }\n        else\n        {\n            low[node] = min(low[node] , low[it]);\n        }\n    }\n}\n    vector<vector<int>> criticalConnections(int n, vector<vector<int>>& con) {\n        vector<int>adj[n];\n        for(int i =  0;i<con.size();i++)\n        {\n            adj[con[i][0]].push_back(con[i][1]);\n            adj[con[i][1]].push_back(con[i][0]);\n        }\n        vector<vector<int>>ans;\n        vector<int>vis(n , 0) , tin(n , 0) , low(n , 0);\n        dfs(adj ,  0 , -1 , tin , low , vis , ans);\n        return ans;\n    }\n};\n```
['Depth-First Search', 'Graph', 'Biconnected Component', 'C++']