Detailed Explanation | Critical Connections in a Network | Tarjan's Algorithm
Approach\nThis problem requires us to find critical connections in a network, removing which some server might not be able to reach some other server. The gist 
**Approach**\nThis problem requires us to find critical connections in a network, removing which some server might not be able to reach some other server. The gist is we have to find bridges in an undirected graph. What we can use for that? **Tarjan\'s Algorithm!**\n\n**What is Tarjan\'s Algorithm?**\nTarjan\'s Algorithm helps us to find strongly connected components in a graph, articulation points and bridges in a graph. Here we keep track of parent of every node, the lowlink value for every node and the id of the node. Initially, we intialise all the parents, lowlink values and id of every node as -1. When the id of a node is -1, it means that the node is not yet visited.\n\npar[node] => Denotes the parent of the node\nid[node] => Denotes the id of the node\nlow[node] => Denotes the lowlink value of the node, i.e., lowest id number of the nodes associated with it\ntime => Denotes the time at which node gets visited (1st node gets visited at 0, it\'s neighbours get visited at 1 and so on..)\n\nWhen we visit a node, we assign the lowlink value and id number to it. Since the id number is no more negative, it also shows that node is visited now. Now we traverse the adjacent nodes of the given node. \n\nIf any adjacent (u) is unvisited, we mark this node as it\'s (u)\'s parent and perform a DFS on it. After that we minimise the given node\'s lowlink value with this adjacent node(u)\'s lowlink value. If the id number of the given node is lesser than lowlink value of its adjacent node, we have found a bridge!\n\nIf the adjacent is visited, we check if its not the parent of given node as parent is also adjacent of node, and if it\'s not, we minimise the lowlink value of node with id number of the adjacent. And we are done!\n\n**Solution**\n```\nclass Solution {\npublic:\n    \n    vector<vector<int>> ans; // required answer\n    vector<vector<int>> adj; // undirected graph\n    vector<int> id; // id number\n    vector<int> low; // lowlink value\n    vector<int> par; // parent\n    int time=0; // time\n    \n    void dfs(int node){\n        id[node]=low[node]=time++; // incrementing time after each node gets visited\n        for(int &u:adj[node]) //exploring all the adjacent nodes of node\n        {\n            if(id[u]==-1) // checking if adjacent node is unvisited\n            {\n                par[u]=node; // assigning node as parent of adjacent node\n                dfs(u); // performing dfs for adjacent node\n                low[node]=min(low[node],low[u]); // minimising lowlink value of node\n                if(id[node]<low[u]) // checking if we have a bridge yet\n                    ans.push_back({node,u});\n            }\n            else if(u!=par[node]) // checking if adjacent is not parent of node\n                low[node]=min(low[node],id[u]); // minimising lowlink value of node\n        }\n    }\n    \n    vector<vector<int>> criticalConnections(int n, vector<vector<int>>& connections) {\n        adj.resize(n);\n        par.resize(n,-1);\n        low.resize(n,-1);\n        id.resize(n,-1);\n        for(int i=0;i<connections.size();i++){ // building our graph\n            adj[connections[i][0]].push_back(connections[i][1]); \n            adj[connections[i][1]].push_back(connections[i][0]);\n        }\n        for(int i=0;i<n;i++) // performing dfs on unvisited nodes\n        {\n            if(id[i]==-1)\n                dfs(i);\n        }\n        return ans;\n    }\n};\n```\n\n**Time Complexity**: O(V+E) (No. of Vertices + No. of Edges)\n
['Graph', 'C']