SHARE
TWEET

Untitled

SalmaYasser Oct 23rd, 2019 120 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. class Solution {
  2.     map<int,vector<int>> adjlist;
  3.     int min_t=INT_MAX;
  4.     int vis[100000]={0};
  5.     int in[100000]={};
  6.     int low_in[100000]={};
  7.     int parent[100000]={};
  8.     int t=1;
  9.     vector<vector<int>> v;
  10. public:
  11.      void dfs_helper(int node)
  12.      {
  13.          vis[node]=1;
  14.          in[node]=t; low_in[node]=t; t++;
  15.          for(auto neigh:adjlist[node])
  16.          {
  17.              parent[neigh]=node;
  18.              if(vis[neigh]&&parent[node]!=neigh)
  19.                  low_in[node]=min(in[neigh],low_in[node]);
  20.              else if(!vis[neigh])
  21.              {
  22.                  dfs_helper(neigh);
  23.                  low_in[node]=min(low_in[node],low_in[neigh]);
  24.                  if(in[node]<low_in[neigh])
  25.                     v.push_back({node,neigh});  
  26.              }
  27.          }
  28.      }
  29.          
  30.      vector<vector<int>> criticalConnections(int n, vector<vector<int>>& connections) {
  31.         for(int i=0;i<connections.size();i++)
  32.         {
  33.             adjlist[connections[i][0]].push_back(connections[i][1]);
  34.             adjlist[connections[i][1]].push_back(connections[i][0]);
  35.         }
  36.         for(auto node: adjlist)
  37.         {
  38.             parent[node.first]=node.first;
  39.             if(!vis[node.first])
  40.               dfs_helper(node.first);
  41.         }
  42.         return v;
  43.       }
  44. };
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top