# Leetcode Question

**1192\. Critical Connections in a Network**

In this problem we have to find the bridges in a graph which are called critical connections in this problem, bridges are edges in a graph on whose removal the graph is broken down into two or more components.

![](https://cdn.hashnode.com/res/hashnode/image/upload/v1683361215157/6b78afe0-4c11-445d-b0a4-3e57fe2ec33e.png align="center")

To solve this question we will use dfs approach along with that we will use two extra arrays.

1. int t\_in\[\]: this array will store the time at which any node is reached. For eg we start from node 1 at time=1 then we will reach node 2 at time=3 and so on...
    
2. int low\_t\_in\[\]: this array will store the lowest time of insertion by checking its adjacent nodes.
    

one thing to note is the condition for which a bridge exists between two nodes and that is if low\_t\_in\[it\]>t\_in\[node\] then the bridge exists and we can remove it, here it is adjacent nodes of that particular node.

```cpp
class Solution {
public:
    
    int timer=1;
    void dfs(int node,int parent,vector<int>& vis,vector<int> adj[],int tin[],int low[],vector<vector<int>>& bridges)
    {
        vis[node]=1;
        tin[node]=low[node]=timer;
        timer++;

        for(auto it:adj[node])
        {
            if(it==parent)  continue;

            if(vis[it]==0)
            {
                dfs(it,node,vis,adj,tin,low,bridges);
                low[node]=min(low[it],low[node]);
                // it-----node

                if(low[it]>tin[node])
                {
                    bridges.push_back({it,node});
                }  

            }
            else
            {
                low[node]=min(low[node],low[it]);
            }
        }
    }
    vector<vector<int>> criticalConnections(int n, vector<vector<int>>& connections) 
    {
        vector<vector<int>> bridges;

       int m = connections.size();

       vector<int> adj[n];
       for(int i=0;i<m;i++)
       {
           int first=connections[i][0];
           int second=connections[i][1];

           adj[first].push_back(second);
           adj[second].push_back(first);
       }

       vector<int> vis(n,0);
       int tin[n];
       int low[n];

       dfs(0,-1,vis,adj,tin,low,bridges);

       return bridges;

    }
};
```