• Sign Up
• Login
• API
• FAQ
• Tools
• Archive
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.

Top