✅Tarjan's Algo || ✅DFS || ❤C++ || ✨Intuition of Tarjan's algo (video link)❤
Really good video for intuition of Tarjan\'s Algorithm\nhttps://www.youtube.com/watch?v=Rhxs4k6DyMM\n\nTime Complexity : O(V + E)\n\n\nclass Solution {\n    voi
Really good video for intuition of **Tarjan\'s Algorithm**\nhttps://www.youtube.com/watch?v=Rhxs4k6DyMM\n\n**Time Complexity : O(V + E)**\n\n```\nclass Solution {\n    void criticalDFS(int node,int time,vector<int>&disc,vector<int>&low,vector<int>&parent,\n                     vector<vector<int>>&adj,vector<vector<int>>&ans){\n        \n        disc[node] = low[node] = time++;\n        \n        for(auto child : adj[node]){\n            //if node has not been visited before\n\t\t\n            if(disc[child] == -1){\n\t\t\t\n\t\t\t   //update parent information for child node\n                parent[child] = node;\n\t\t\t\t\n                criticalDFS(child,time,disc,low,parent,adj,ans);\n                \n\t\t\t\t//while backtracking, update low value of parent to check if there is a back-edge\n                low[node] = min(low[node],low[child]);\n                \n\t\t\t\t//check if the edge is a bridge and not a back-edge from child/sub-graph of child\n                //to it\'s parent or any of it\'s ancestors\n                if(low[child] > disc[node]){\n                    ans.push_back({node,child});\n                }\n            }\n\t\t\t\n\t\t\t//check just for a single back-edge\n            else if(child != parent[node]){\n\t\t\t    //check and update if the ancestor was discovered before the earliest connected node to our current node\n                low[node] = min(low[node],disc[child]);\n            }\n        }\n    }\n    \n    \npublic:\n    vector<vector<int>> criticalConnections(int n, vector<vector<int>>& connections) {\n\n        vector<vector<int>>ans;\n        vector<int>disc(n,-1);\n        vector<int>low(n,-1);\n        vector<int>parent(n,-1);\n        \n        //build undirected graph\n        vector<vector<int>>adj(n);\n        for(auto it : connections){\n            adj[it[1]].push_back(it[0]);\n            adj[it[0]].push_back(it[1]);\n        }\n        for(int i=0;i<n;i++){\n            if(disc[i] == -1){\n                criticalDFS(i,0,disc,low,parent,adj,ans);\n            }\n        }\n        return ans;\n    }\n};\n```
['Depth-First Search', 'C']