nikunjsoni

1192

Jun 25th, 2021
85
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. class Solution {
  2. public:
  3.     int n; // number of nodes
  4.     vector<vector<int>> adj; // adjacency list of graph
  5.     vector<vector<int>> bridges;
  6.     vector<bool> visited;
  7.     vector<int> tin, low;
  8.     int timer;
  9.    
  10.     vector<vector<int>> criticalConnections(int N, vector<vector<int>>& connections) {
  11.         n = N;
  12.         adj.resize(n);
  13.         visited.assign(n, false);
  14.         tin.resize(n);
  15.         low.resize(n);
  16.         for(auto edge: connections){
  17.             adj[edge[0]].push_back(edge[1]);
  18.             adj[edge[1]].push_back(edge[0]);
  19.         }
  20.         find_bridges();
  21.         return bridges;
  22.     }
  23.    
  24.     void dfs(int v, int p = -1){
  25.         visited[v] = true;
  26.         tin[v] = low[v] = timer++;
  27.         for(int to : adj[v]) {
  28.             if (to == p) continue;
  29.             if(visited[to]) {
  30.                 low[v] = min(low[v], tin[to]);
  31.             }
  32.             else{
  33.                 dfs(to, v);
  34.                 low[v] = min(low[v], low[to]);
  35.                 if(low[to] > tin[v])
  36.                     bridges.push_back({v, to});
  37.             }
  38.         }
  39.     }
  40.  
  41.     void find_bridges(){
  42.         timer = 0;
  43.         for(int i = 0; i < n; ++i) {
  44.             if(!visited[i])
  45.                 dfs(i);
  46.         }
  47.     }
  48. };
RAW Paste Data