1192

class Solution {
public:
    int n; // number of nodes
    vector<vector<int>> adj; // adjacency list of graph
    vector<vector<int>> bridges;
    vector<bool> visited;
    vector<int> tin, low;
    int timer;

    vector<vector<int>> criticalConnections(int N, vector<vector<int>>& connections) {
        n = N;
        adj.resize(n);
        visited.assign(n, false);
        tin.resize(n);
        low.resize(n);
        for(auto edge: connections){
            adj[edge[0]].push_back(edge[1]);
            adj[edge[1]].push_back(edge[0]);
        }
        find_bridges();
        return bridges;
    }

    void dfs(int v, int p = -1){
        visited[v] = true;
        tin[v] = low[v] = timer++;
        for(int to : adj[v]) {
            if (to == p) continue;
            if(visited[to]) {
                low[v] = min(low[v], tin[to]);
            }
            else{
                dfs(to, v);
                low[v] = min(low[v], low[to]);
                if(low[to] > tin[v])
                    bridges.push_back({v, to});
            }
        }
    }

    void find_bridges(){
        timer = 0;
        for(int i = 0; i < n; ++i) {
            if(!visited[i])
                dfs(i);
        }
    }
};