#include "leetcode.h" class Solution { public: vector> criticalConnections(int n, vector> &connections) { vector vi(n, false); vector disc(n, 0), low(n, 0), parent(n, -1); vector> g(n, vector()), ans; for (auto &p : connections) { g[p.front()].push_back(p.back()); g[p.back()].push_back(p.front()); } for (int i = 0; i < n; ++i) { if (vi[i]) continue; helper(i, vi, disc, low, parent, g, ans); } return ans; } private: void helper(int u, vector &vi, vector &disc, vector &low, vector &parent, vector> &g, vector> &ans) { static int time = 0; vi[u] = true; disc[u] = low[u] = ++time; for (int i : g[u]) { if (!vi[i]) { parent[i] = u; helper(i, vi, disc, low, parent, g, ans); low[u] = min(low[u], low[i]); if (low[i] > disc[u]) ans.push_back({u, i}); } else if (i != parent[u]) low[u] = min(low[u], disc[i]); } } }; int main() {}