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.

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.

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;

    }
};