• API
• FAQ
• Tools
• Archive
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.
Not a member of Pastebin yet?