Let's discuss how to find critical connections in a network.

Naive Approach

A straightforward but inefficient approach would be to iterate through each connection, remove it temporarily, and then check if the graph remains connected. If removing the connection disconnects the graph, then it's a critical connection.

1. Iterate through each connection.
2. Temporarily remove the connection from the graph.
3. Perform a Depth-First Search (DFS) or Breadth-First Search (BFS) to check if the graph is still connected. Start from any node and see if we can reach all other nodes.
4. If the graph is disconnected, the removed connection is critical.
5. Restore the connection to the graph.

Big O Analysis (Naive Approach)

• Time Complexity: O(E * (V + E)), where E is the number of edges (connections) and V is the number of vertices (servers). For each edge, we perform a graph traversal (DFS or BFS), which takes O(V + E) time.
• Space Complexity: O(V + E) to store the graph.

This approach is too slow for large graphs due to repeated graph traversals.

Optimal Approach: Tarjan's Algorithm

A more efficient solution uses Tarjan's algorithm, which is based on Depth-First Search (DFS). It identifies critical connections (also known as bridges) in O(V + E) time.

The key idea is to maintain two arrays:

• disc[u]: Discovery time of node u during DFS.
• low[u]: The lowest discovery time of any node reachable from u (including u itself) through the DFS subtree.

Here's how it works:

1. Initialization:
   • Initialize disc[u] and low[u] to -1 for all nodes.
   • Initialize time to 0.
2. DFS Traversal:
   • Start DFS from an arbitrary node.
   • For each node u:
     • disc[u] = low[u] = time++
     • For each neighbor v of u:
       • If v is not visited:
         • Recursively call DFS on v.
         • low[u] = min(low[u], low[v])
         • If low[v] > disc[u], then the edge (u, v) is a critical connection.
       • Else if v is not the parent of u in the DFS tree (to avoid back-tracking immediately):
         • low[u] = min(low[u], disc[v])

Big O Analysis (Tarjan's Algorithm)

• Time Complexity: O(V + E), where V is the number of vertices and E is the number of edges. DFS visits each node and edge once.
• Space Complexity: O(V) to store the disc, low, and visited arrays, and the recursion stack.

Edge Cases

• Empty Graph: If the graph has no nodes or edges, return an empty list.
• Single Node: If the graph has only one node, there are no connections, so return an empty list.
• Disconnected Graph: Tarjan's algorithm will work correctly even for disconnected graphs; it will find critical connections in each connected component.
• Graph with no critical connections: Algorithm should return empty list.

Code Implementation (Python)

from collections import defaultdict

def criticalConnections(n, connections):
    graph = defaultdict(list)
    for u, v in connections:
        graph[u].append(v)
        graph[v].append(u)

    disc = [-1] * n
    low = [-1] * n
    time = 0
    result = []

    def dfs(u, parent):
        nonlocal time
        disc[u] = low[u] = time
        time += 1

        for v in graph[u]:
            if v == parent:
                continue

            if disc[v] == -1:
                dfs(v, u)
                low[u] = min(low[u], low[v])
                if low[v] > disc[u]:
                    result.append([u, v])
            else:
                low[u] = min(low[u], disc[v])

    dfs(0, -1)  # Start DFS from node 0
    return result

In summary, Tarjan's algorithm provides an efficient way to find critical connections in a graph by leveraging DFS and tracking discovery times and low-link values.