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.

&nbsp;
Example 1:

Input: n = 4, connections = [[0,1],[1,2],[2,0],[1,3]]
Output: [[1,3]]
Explanation: [[3,1]] is also accepted.


Example 2:

Input: n = 2, connections = [[0,1]]
Output: [[0,1]]


&nbsp;
Constraints:


	2 &lt;= n &lt;= 105
	n - 1 &lt;= connections.length &lt;= 105
	0 &lt;= ai, bi &lt;= n - 1
	ai != bi
	There are no repeated connections.


class Solution:
    def criticalConnections(self, n: int, connections: List[List[int]]) -> List[List[int]]:
        
        dic = collections.defaultdict(list)
        for c in connections:
            u, v = c
            dic[u].append(v)
            dic[v].append(u)
            
        
        timer = 0
        
        depth, lowest, parent, visited = [float("inf")]*n, [float("inf")]*n, [float("inf")]*n, [False]*n
        res = []
        
        def find(u):
            
            nonlocal timer
            
            visited[u] = True
            depth[u], lowest[u] = timer, timer
            timer += 1
            
            for v in dic[u]:   
                
                if not visited[v]:
                    parent[v] = u
                    find(v)
                    if lowest[v]>depth[u]:
                        res.append([u,v])
                
                if parent[u]!=v:
                    lowest[u] = min(lowest[u], lowest[v])
                
        find(0)
        return res
        
class Solution {
    // We record the timestamp that we visit each node. For each node, we check every neighbor except its parent and return a smallest timestamp in all its neighbors. If this timestamp is strictly less than the node's timestamp, we know that this node is somehow in a cycle. Otherwise, this edge from the parent to this node is a critical connection
    public List<List<Integer>> criticalConnections(int n, List<List<Integer>> connections) {
        List<Integer>[] graph = new ArrayList[n];
        for (int i = 0; i < n; i++) graph[i] = new ArrayList<>();
        
        for(List<Integer> oneConnection :connections) {
            graph[oneConnection.get(0)].add(oneConnection.get(1));
            graph[oneConnection.get(1)].add(oneConnection.get(0));
        }
        int timer[] = new int[1];
        List<List<Integer>> results = new ArrayList<>();
        boolean[] visited = new boolean[n];
        int []timeStampAtThatNode = new int[n]; 
        criticalConnectionsUtil(graph, -1, 0, timer, visited, results, timeStampAtThatNode);
        return results;
    }
    
    
    public void criticalConnectionsUtil(List<Integer>[] graph, int parent, int node, int timer[], boolean[] visited, List<List<Integer>> results, int []timeStampAtThatNode) {
        visited[node] = true;
        timeStampAtThatNode[node] = timer[0]++;
        int currentTimeStamp = timeStampAtThatNode[node];
        
        for(int oneNeighbour : graph[node]) {
            if(oneNeighbour == parent) continue;
            if(!visited[oneNeighbour]) criticalConnectionsUtil(graph, node, oneNeighbour, timer, visited, results, timeStampAtThatNode);
            timeStampAtThatNode[node] = Math.min(timeStampAtThatNode[node], timeStampAtThatNode[oneNeighbour]);
            if(currentTimeStamp < timeStampAtThatNode[oneNeighbour]) results.add(Arrays.asList(node, oneNeighbour));
        }
        
        
    }
    
}
class Solution {
    int timer = 1;
public:
void dfs(vector<int>adj[] , int node , int parent , vector<int>&tin , vector<int>&low , vector<int>&vis , vector<vector<int>>&ans)
{
    vis[node] = 1;
    tin[node] = low[node] = timer;
    timer++;
    for(auto it:adj[node])
    {
        if(it == parent) continue;
        if(vis[it] == 0)
        {
            dfs(adj , it , node , tin , low , vis , ans);
            low[node] = min(low[node] , low[it]);
            if(tin[node] < low[it])
            ans.push_back({node , it});
        }
        else
        {
            low[node] = min(low[node] , low[it]);
        }
    }
}
    vector<vector<int>> criticalConnections(int n, vector<vector<int>>& con) {
        vector<int>adj[n];
        for(int i =  0;i<con.size();i++)
        {
            adj[con[i][0]].push_back(con[i][1]);
            adj[con[i][1]].push_back(con[i][0]);
        }
        vector<vector<int>>ans;
        vector<int>vis(n , 0) , tin(n , 0) , low(n , 0);
        dfs(adj ,  0 , -1 , tin , low , vis , ans);
        return ans;
    }
};
var criticalConnections = function(n, connections) {
    // Graph Formation
    const graph = new Map();
    connections.forEach(([a, b]) => {
        const aconn = graph.get(a) || [];
        const bconn = graph.get(b) || [];

        aconn.push(b), bconn.push(a);
        graph.set(a, aconn);
        graph.set(b, bconn);
    });

    // Find Bridges
    const bridges = [];
    const visited = new Array(n).fill(false);
    const tin = new Array(n).fill(-1);
    const dis = new Array(n).fill(-1);

    let time = 0;

    const dfs = (node, parent = -1) => {
        visited[node] = true;
        ++time;
        tin[node] = time;
        dis[node] = time;

        const connections = graph.get(node);
        for(let conn of connections) {
            if(conn == parent) {
                continue;
            }
            if(visited[conn]) {
                dis[node] = Math.min(dis[node], tin[conn]);
            } else {
                dfs(conn, node);
                dis[node] = Math.min(dis[node], dis[conn]);
                if(dis[conn] > tin[node]) {
                    bridges.push([node, conn]);
                }
            }
        };
    }

    dfs(0);

    return bridges;
};
Critical Connections in a Network