Critical Connections in a Network

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

A critical connection is a connection that, if removed, will make some servers unable to reach some other server.

Return all critical connections in the network in any order.

Example 1:

Input: n = 4, connections = [[0,1],[1,2],[2,0],[1,3]]
Output: [[1,3]]
Explanation: [[3,1]] is also accepted.

Example 2:

Input: n = 2, connections = [[0,1]]
Output: [[0,1]]

Constraints:

• 2 <= n <= 10^5
• n - 1 <= connections.length <= 10^5
• 0 <= a_i, b_i <= n - 1
• a_i != b_i
• There are no repeated connections.

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

class Solution {
public:
    vector<vector<int>> criticalConnections(int n, vector<vector<int>>& connections) {
        vector<vector<int>> adj(n);
        for (const auto& connection : connections) {
            adj[connection[0]].push_back(connection[1]);
            adj[connection[1]].push_back(connection[0]);
        }

        vector<int> disc(n, -1); // Discovery time of each node
        vector<int> low(n, -1);  // Lowest reachable ancestor from each node
        vector<vector<int>> result; // Store critical connections
        int time = 0;

        function<void(int, int)> dfs = [&](int u, int parent) {
            disc[u] = low[u] = ++time;

            for (int v : adj[u]) {
                if (v == parent) continue; // Ignore the parent in DFS

                if (disc[v] == -1) { // If v is not visited
                    dfs(v, u);
                    low[u] = min(low[u], low[v]);

                    // If the lowest reachable ancestor of v is greater than the discovery time of u,
                    // then (u, v) is a critical connection
                    if (low[v] > disc[u]) {
                        result.push_back({u, v});
                    }
                } else { // If v is already visited
                    low[u] = min(low[u], disc[v]);
                }
            }
        };

        dfs(0, -1); // Start DFS from node 0 with no parent

        return result;
    }
};

/*

Naive Approach:

For each edge (u, v), remove it from the graph.
Check if the graph is still connected. This can be done using BFS or DFS.
If the graph is disconnected after removing the edge, then (u, v) is a critical connection.

Time Complexity: O(E * (V + E)), where E is the number of edges and V is the number of vertices.
Space Complexity: O(V + E)

Optimal Approach:

Use Tarjan's Algorithm to find critical connections (bridges) in the graph.
Tarjan's algorithm is based on the concept of discovery time and lowest reachable ancestor.
Discovery time (disc[u]) is the time when a node u is first visited during DFS.
Lowest reachable ancestor (low[u]) is the lowest discovery time of any node reachable from u.
An edge (u, v) is a critical connection if low[v] > disc[u].

Time Complexity: O(V + E)
Space Complexity: O(V)

*/

int main() {
    Solution sol;
    int n = 4;
    vector<vector<int>> connections = {{0,1},{1,2},{2,0},{1,3}};
    vector<vector<int>> result = sol.criticalConnections(n, connections);

    cout << "Critical Connections:" << endl;
    for (const auto& connection : result) {
        cout << "[" << connection[0] << ", " << connection[1] << "]" << endl;
    }

    return 0;
}

Explanation:

The problem asks us to find the critical connections in a network of servers. A critical connection is one that, if removed, would disconnect the network. We can solve this problem efficiently using Tarjan's algorithm.

Naive Approach

1. For each edge (u, v):
   • Remove the edge (u, v) from the graph.
   • Check if the graph is still connected using BFS or DFS.
   • If the graph is disconnected, then (u, v) is a critical connection.

This approach is simple to understand but inefficient because for each edge, we have to perform a graph traversal.

Optimal Approach (Tarjan's Algorithm)

Tarjan's algorithm leverages the concept of discovery time and lowest reachable ancestor to identify critical connections (bridges) in a graph.

1. Initialization:

   • disc[u]: Discovery time of node u.
   • low[u]: Lowest reachable ancestor from node u.
   • time: A counter to track discovery time.

2. DFS Traversal:

   • Start DFS from an arbitrary node.
   • For each node u, update disc[u] and low[u] to the current time.
   • For each neighbor v of u:
     • If v is the parent of u, ignore it.
     • If v is not visited, recursively call DFS on v.
       • After the recursive call, update low[u] to the minimum of low[u] and low[v].
       • If low[v] > disc[u], then the edge (u, v) is a critical connection.
     • If v is already visited, update low[u] to the minimum of low[u] and disc[v].

3. Critical Connection Identification:

   • An edge (u, v) is a critical connection if low[v] > disc[u]. This condition implies that there is no back-edge from the subtree rooted at v to any ancestor of u. Hence, removing the edge (u, v) will disconnect the subtree rooted at v from the rest of the graph.

Example

Consider the example: n = 4, connections = [[0,1],[1,2],[2,0],[1,3]]

1. Adjacency List:

   0: [1, 2]
   1: [0, 2, 3]
   2: [1, 0]
   3: [1]
   

2. DFS Traversal:

   • Start DFS from node 0.
   • disc[0] = 1, low[0] = 1
   • Visit node 1.
   • disc[1] = 2, low[1] = 2
   • Visit node 2.
   • disc[2] = 3, low[2] = 3
   • Visit node 0 (already visited).
   • low[2] = min(3, 1) = 1
   • Backtrack to node 1.
   • low[1] = min(2, 1) = 1
   • Visit node 3.
   • disc[3] = 4, low[3] = 4
   • Backtrack to node 1.
   • low[1] = min(1, 4) = 1
   • Backtrack to node 0.

3. Critical Connection:

   • Edge (1, 3) is a critical connection because low[3] = 4 > disc[1] = 2.

Big(O) Runtime Analysis

The optimal approach uses Tarjan's Algorithm which involves a single Depth-First Search (DFS) traversal of the graph. Each node and each edge are visited once.

• Time Complexity: O(V + E), where V is the number of vertices (servers) and E is the number of edges (connections). This is because the DFS traversal visits each vertex and edge once.

Big(O) Space Usage Analysis

• Space Complexity: O(V), where V is the number of vertices (servers). This is due to the space required for:
  • adj (adjacency list): O(E) in the worst case (dense graph).
  • disc array: O(V).
  • low array: O(V).
  • Recursion stack for DFS: O(V) in the worst case (e.g., a skewed tree).
  • result vector in worst case will contain all the edges making it O(E). However since E <= 10^5 and V <= 10^5, we can consider this to be O(V).

Edge Cases

1. Empty Graph:

   • If the graph is empty (no connections), there are no critical connections. The algorithm should return an empty list.

2. Single Node Graph:

   • If the graph has only one node, there are no connections, and therefore no critical connections. Return an empty list.

3. Disconnected Graph:

   • If the graph is disconnected, the algorithm will still correctly identify critical connections within each connected component.

4. Graph with Self-Loops or Parallel Edges:

   • The problem statement specifies that there are no repeated connections. However, if self-loops or parallel edges exist, the algorithm should handle them correctly. Self-loops do not affect the critical connections, and parallel edges should be considered only once.

5. Large Graph:

   • For very large graphs (e.g., V = 10^5, E = 10^5), the algorithm should be efficient enough to run within the time limit. Tarjan's algorithm is well-suited for such cases due to its linear time complexity.

6. Already a tree:

   • If the graph is already a tree, then all edges are critical connections. The algorithm will correctly identify all the edges as critical connections.

This comprehensive explanation covers the algorithm, its complexity, and various edge cases, ensuring a thorough understanding of the problem and its solution.