1192. Critical Connections in a Network.cpp

class Solution {
public:
    vector<vector<int>> ans;
    vector<vector<int>> graph;
    vector<int> id;
    vector<int> lowlink;
    vector<bool> vis;
    int time=0;
    
    void DFS(int node,int parent){
        id[node]=lowlink[node]=time++;
        vis[node]=true;
        for(int &x : graph[node]){
            if(parent==x) continue;
            if(vis[x]==false){
                DFS(x, node);
                lowlink[node] = min(lowlink[node], lowlink[x]);
                if(id[node] < lowlink[x]){
                    ans.push_back({node, x});
                }
            }
            else{
                lowlink[node]=min(lowlink[node],id[x]);
            }
        }
    }
    
    vector<vector<int>> criticalConnections(int n, vector<vector<int>>& connections) {
        graph.resize(n);
        vis.resize(n,false);
        lowlink.resize(n,0);
        id.resize(n,0);
        for(auto &x : connections){
            graph[x[0]].push_back(x[1]);
            graph[x[1]].push_back(x[0]);
        }
        for(int i = 0; i < n; ++i){
            if(vis[i]==false) DFS(i, i);
        }
        return ans;
    }
};