SHARE
TWEET

Untitled

a guest Sep 15th, 2019 89 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. class Solution {
  2.     vector<int> status;
  3.     vector<int> visOrder;
  4.     vector<int> reach; // reach[i]: farthest ancestor that i can reach in dfs tree
  5.     vector<vector<int>> graph;
  6.     int seqCount;
  7.    
  8.     int dfs(int node, int parent) {
  9.         visOrder[node] = seqCount ++;
  10.         status[node] = 1;
  11.         int ancestor = node;
  12.         for (auto next : graph[node]) {
  13.             if (next == parent)
  14.                 continue;
  15.             int tmp = next;
  16.             if (status[tmp] == 0) {
  17.                 tmp = dfs(tmp, node);
  18.             }
  19.             if (visOrder[tmp] <= visOrder[ancestor]) {
  20.                 ancestor = tmp;
  21.             }
  22.         }
  23.         //status[node] = 2;
  24.         reach[node] = ancestor;
  25.         return ancestor;
  26.     }
  27.     void init(int n, vector<vector<int>>& connections) {
  28.         status.resize(n, 0);
  29.         visOrder.resize(n, INT_MAX);
  30.         reach.resize(n);
  31.         seqCount = 0;
  32.         graph.resize(n);
  33.         for (auto & conn : connections) {
  34.             graph[conn[0]].push_back(conn[1]);
  35.             graph[conn[1]].push_back(conn[0]);
  36.         }
  37.     }
  38. public:
  39.     vector<vector<int>> criticalConnections(int n, vector<vector<int>>& connections) {
  40.         init(n, connections);
  41.         dfs(0, -1);
  42.         vector<vector<int>> res;
  43.         for (auto & conn: connections) {
  44.             if (visOrder[conn[0]] < visOrder[conn[1]] && visOrder[reach[conn[1]]] < visOrder[conn[1]])
  45.                 continue;
  46.             if (visOrder[conn[1]] < visOrder[conn[0]] && visOrder[reach[conn[0]]] < visOrder[conn[0]])
  47.                 continue;
  48.             res.push_back(conn);
  49.         }
  50.         return res;
  51.     }
  52. };
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
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!
 
Top