✅C++ || Striver's Solution || Bridges in Graph
\n\nT->O(n+2e) [Same as DFS Algo] && S->O(n+ 2e)+O(3n)\nThis is the direct question on Tarjan\'s Algo (Bridges in Graph)\n\n\tclass Solution {\n\t\tpublic:\n\n\
![image](https://assets.leetcode.com/users/images/7484b93c-1e5b-4152-a851-7756d22b99cb_1672603201.9800382.png)\n\n**T->O(n+2e) [Same as DFS Algo] && S->O(n+ 2e)+O(3n)**\n***This is the direct question on Tarjan\'s Algo (Bridges in Graph)***\n\n\tclass Solution {\n\t\tpublic:\n\n\t\t\tint timer = 1;\n\n\t\t\tvoid dfs(int node,int parent,vector<int> adj[],vector<int>& vis,vector<int>& tin,vector<int>& low,vector<vector<int>>& bridges){\n\n\t\t\t\tvis[node] = 1;\n\t\t\t\ttin[node] = low[node] = timer; \n\t\t\t\ttimer++;\n\n\t\t\t\tfor(auto it : adj[node]){\n\t\t\t\t\tif(it == parent) continue;\n\n\t\t\t\t\tif(!vis[it]){\n\t\t\t\t\t\tdfs(it,node,adj,vis,tin,low,bridges);\n\t\t\t\t\t\tlow[node] = min(low[node],low[it]);\n\n\t\t\t\t\t\t// Can this edge (node--it) be a bridge?\n\t\t\t\t\t\tif(low[it] > tin[node]) bridges.push_back({it,node});\n\t\t\t\t\t}\n\t\t\t\t\telse low[node] = min(low[node],low[it]);\n\t\t\t\t}\n\t\t\t}\n\n\t\t\tvector<vector<int>> criticalConnections(int n, vector<vector<int>>& connections) {\n\n\t\t\t\tvector<int> adj[n];\n\t\t\t\tfor(int i = 0 ; i < connections.size() ; i++){\n\t\t\t\t\tint u = connections[i][0];\n\t\t\t\t\tint v = connections[i][1];\n\t\t\t\t\tadj[u].push_back(v);\n\t\t\t\t\tadj[v].push_back(u);\n\t\t\t\t}\n\n\t\t\t\tvector<vector<int>> bridges;\n\t\t\t\tvector<int> vis(n, 0);\n\t\t\t\tvector<int> tin(n);\n\t\t\t\tvector<int> low(n);\n\t\t\t\tdfs(0,-1,adj,vis,tin,low,bridges);\n\n\t\t\t\treturn bridges;\n\t\t\t}\n\t\t\t};
['Depth-First Search', 'C', 'C++']