<p>There are <code>n</code> servers numbered from <code>0</code> to <code>n - 1</code> connected by undirected server-to-server <code>connections</code> forming a network where <code>connections[i] = [a<sub>i</sub>, b<sub>i</sub>]</code> represents a connection between servers <code>a<sub>i</sub></code> and <code>b<sub>i</sub></code>. Any server can reach other servers directly or indirectly through the network.</p>

<p>A <em>critical connection</em> is a connection that, if removed, will make some servers unable to reach some other server.</p>

<p>Return all critical connections in the network in any order.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2019/09/03/1537_ex1_2.png" style="width: 198px; height: 248px;" />
<pre>
<strong>Input:</strong> n = 4, connections = [[0,1],[1,2],[2,0],[1,3]]
<strong>Output:</strong> [[1,3]]
<strong>Explanation:</strong> [[3,1]] is also accepted.
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> n = 2, connections = [[0,1]]
<strong>Output:</strong> [[0,1]]
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>2 &lt;= n &lt;= 10<sup>5</sup></code></li>
	<li><code>n - 1 &lt;= connections.length &lt;= 10<sup>5</sup></code></li>
	<li><code>0 &lt;= a<sub>i</sub>, b<sub>i</sub> &lt;= n - 1</code></li>
	<li><code>a<sub>i</sub> != b<sub>i</sub></code></li>
	<li>There are no repeated connections.</li>
</ul>

class Solution {
public:
    vector<vector<int>> criticalConnections(int n, vector<vector<int>>& connections) {
        // Helper function to create the graph
        auto makeGraph = [&](const vector<vector<int>>& connections) {
            unordered_map<int, vector<int>> graph;
            for (const auto& conn : connections) {
                graph[conn[0]].push_back(conn[1]);
                graph[conn[1]].push_back(conn[0]);
            }
            return graph;
        };

        // Create the graph
        auto graph = makeGraph(connections);

        // Convert connections to a set of sorted tuples
        unordered_set<pair<int, int>, hash_pair> connectionSet;
        for (auto& conn : connections) {
            sort(conn.begin(), conn.end());
            connectionSet.insert({conn[0], conn[1]});
        }

        vector<int> rank(n, -2);

        function<int(int, int)> dfs = [&](int node, int depth) {
            if (rank[node] >= 0) {
                return rank[node]; // visiting (0<=rank<n), or visited (rank=n)
            }
            rank[node] = depth;
            int minBackDepth = n;
            for (const int& neighbor : graph[node]) {
                if (rank[neighbor] == depth - 1) continue; // don't immediately go back to parent
                int backDepth = dfs(neighbor, depth + 1);
                if (backDepth <= depth) {
                    connectionSet.erase({min(node, neighbor), max(node, neighbor)});
                }
                minBackDepth = min(minBackDepth, backDepth);
            }
            rank[node] = n; // this line is not necessary
            return minBackDepth;
        };

        // Perform DFS
        dfs(0, 0);

        // Convert set back to vector of vectors
        vector<vector<int>> result;
        for (const auto& conn : connectionSet) {
            result.push_back({conn.first, conn.second});
        }

        return result;
    }

private:
    struct hash_pair {
        template <class T1, class T2>
        size_t operator()(const pair<T1, T2>& p) const {
            auto hash1 = hash<T1>{}(p.first);
            auto hash2 = hash<T2>{}(p.second);
            return hash1 ^ hash2;
        }
    };
};
212098