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.

For example: n = 4, connections = [[0,1],[1,2],[2,0],[1,3]] Output: [[1,3]]

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.

## Critical Connections in a Network

This problem asks us to find the critical connections in a given network. A critical connection is one that, if removed, would disconnect the network, making some servers unreachable from others.

### Naive Approach (Brute Force)

One simple approach is to iterate through each connection, remove it from the graph, and then check if the graph is still connected. If the graph becomes disconnected after removing a connection, then that connection is critical.

**Code (Python):**

```python
def is_connected(n, adj):  # Helper function to check connectivity
    visited = [False] * n
    q = [0]  # Start BFS from node 0
    visited[0] = True
    count = 0

    while q:
        u = q.pop(0)
        count += 1

        for v in adj[u]:
            if not visited[v]:
                visited[v] = True
                q.append(v)

    return count == n


def critical_connections_naive(n, connections):
    critical = []
    for i in range(len(connections)):
        # Remove the connection
        temp_connections = connections[:i] + connections[i+1:]

        # Build adjacency list
        adj = [[] for _ in range(n)]
        for u, v in temp_connections:
            adj[u].append(v)
            adj[v].append(u)

        # Check if the graph is still connected
        if not is_connected(n, adj):
            critical.append(connections[i])

    return critical

# Example Usage
n = 4
connections = [[0, 1], [1, 2], [2, 0], [1, 3]]
result = critical_connections_naive(n, connections)
print(result)  # Output: [[1, 3]]

Optimal Approach (Tarjan's Algorithm)

A more efficient approach is to use Tarjan's algorithm. Tarjan's algorithm is a graph traversal algorithm that can find bridges (critical connections) in a graph in linear time.

Key Concepts in Tarjan's Algorithm:

• DFS (Depth-First Search): We explore the graph using DFS.
• disc[u] (Discovery Time): The time when a node u is first visited during DFS.
• low[u] (Lowest Reachable Ancestor): The lowest discovery time of any node reachable from u through the DFS subtree rooted at u (including back edges).

Algorithm Steps:

1. Initialize disc and low arrays with -1 for all nodes.
2. Start DFS from an arbitrary node.
3. During DFS:
   • Assign a discovery time disc[u] when a node u is visited.
   • Update low[u] with disc[u] initially.
   • For each neighbor v of u:
     • If v is not visited, recursively call DFS on v.
       • After the recursive call, update low[u] = min(low[u], low[v]).
       • If low[v] > disc[u], then the edge (u, v) is a critical connection (bridge).
     • If v is visited and v is not the parent of u in the DFS tree, update low[u] = min(low[u], disc[v]) (back edge).

Code (Python):

def critical_connections(n, connections):
    adj = [[] for _ in range(n)]
    for u, v in connections:
        adj[u].append(v)
        adj[v].append(u)

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

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

        for v in adj[u]:
            if v == parent:
                continue  # Skip the parent

            if disc[v] == -1:
                dfs(v, u)
                low[u] = min(low[u], low[v])
                if low[v] > disc[u]:
                    critical.append([u, v] if u < v else [v, u]) # Ensure consistent ordering
            else:
                low[u] = min(low[u], disc[v])  # Back edge

    for i in range(n):
        if disc[i] == -1:
            dfs(i, -1)

    return critical

# Example Usage
n = 4
connections = [[0, 1], [1, 2], [2, 0], [1, 3]]
result = critical_connections(n, connections)
print(result)  # Output: [[1, 3]]

Big(O) Runtime Analysis

• Naive Approach: The naive approach iterates through each connection (O(E)) and performs a connectivity check (O(V + E)). Therefore, the overall runtime complexity is O(E * (V + E)), where V is the number of vertices (servers) and E is the number of edges (connections). In the worst-case scenario, where E is close to V^2, the runtime becomes O(V^4).
• Tarjan's Algorithm: Tarjan's algorithm performs a single DFS traversal of the graph. DFS takes O(V + E) time. The rest of the operations inside the DFS function (min, comparisons, etc.) take constant time. Therefore, the overall runtime complexity of Tarjan's algorithm is O(V + E), which is linear with respect to the size of the graph.

Big(O) Space Usage Analysis

• Naive Approach: The naive approach requires storing a temporary copy of the connections (O(E)) and an adjacency list (O(V + E)). The visited array in the is_connected function takes O(V) space. Therefore, the overall space complexity is O(V + E).
• Tarjan's Algorithm: Tarjan's algorithm requires storing the adjacency list (O(V + E)), the disc and low arrays (O(V) each), and the critical list to store the results (in the worst case, O(E)). Therefore, the overall space complexity is O(V + E).

Edge Cases

1. Empty Graph: If the graph has no connections, there are no critical connections. The algorithm should return an empty list.
2. Disconnected Graph: If the graph is disconnected to begin with, removing any existing edge would likely further disconnect the graph. However, the problem defines critical connections in the context of an already connected network initially.
3. Graph with No Critical Connections: A complete graph (where every node is connected to every other node) has no critical connections. The algorithm should return an empty list.
4. Self-Loops or Parallel Edges: The problem statement specifies that there are no repeated connections. Self-loops would not be critical connections, as their removal wouldn't disconnect any nodes. The given solution assumes no self-loops or parallel edges.

These edge cases are handled correctly by Tarjan's algorithm.