1192. Critical Connections in a Network

There are n servers numbered from 0 to n - 1 connected by undirected server-to-server connections forming a network where connections[i] = [ai, bi] represents a connection between servers ai and bi. Any server can reach other servers directly or indirectly through the network.

A critical connection is a connection that, if removed, will make some servers unable to reach some other server.

Return all critical connections in the network in any order.

class Solution {
    vector<vector<int>> g;
    
    int gr = 1;
    vector<int> mi, vis;
    vector<vector<vector<int>>> bcc;
    vector<vector<int>> st;
    
    void dfs(int n, int p) {
        mi[n] = vis[n] = gr++;
        for(auto near : g[n]) {
            if(near == p) continue;
            
            if(vis[n] > vis[near]) {
                st.push_back({n,near});
            }
            
            if(vis[near]) {
                mi[n] = min(mi[n], vis[near]);
            } else {
                dfs(near, n);
                mi[n] = min(mi[n], mi[near]);
                if(mi[near] >= vis[n]) {
                    bcc.emplace_back();
                    while(!st.empty()) {
                        auto e = st.back(); st.pop_back();
                        bcc.back().push_back(e);
                        if(e[0] == n and e[1] == near) break;
                    }
                }
            }
        }
    }
public:
    vector<vector<int>> criticalConnections(int n, vector<vector<int>>& connections) {
        g = vector<vector<int>>(n);
        mi = vector<int>(n);
        vis = vector<int>(n);
        for(auto conn : connections) {
            g[conn[0]].push_back(conn[1]);
            g[conn[1]].push_back(conn[0]);
        }
        for(int i = 0; i < n; i++) {
            if(!vis[i])
                dfs(i,-1);
        }
        vector<vector<int>> res;
        for(auto component : bcc) {
            if(component.size() == 1) {
                res.push_back(component[0]);
            }
        }
        return res;
    }
};