# Critical Connections in a Network
**Difficulty:** HARD
[External](https://leetcode.com/problems/critical-connections-in-a-network)
Canonical: https://scaleengineer.com/dsa/problems/critical-connections-in-a-network
**Algorithms:** [Depth-First Search](https://scaleengineer.com/algorithms/depth-first-search)
**Data structures:** Graph
**Companies:** [Akuna Capital](https://scaleengineer.com/companies/akuna-capital)
---
## Problem
There are `n` servers numbered from `0` to `n - 1` connected by undirected server-to-server `connections` forming a network where `connections[i] = [ai, bi]` represents a connection between servers `ai` and `bi`. 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:**

![](https://assets.glich.co/dsa/critical-connections-in-a-network/image0.png) 

**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 <= 105`
* `n - 1 <= connections.length <= 105`
* `0 <= ai, bi <= n - 1`
* `ai != bi`
* There are no repeated connections.

# Approaches
## Brute Force by Removing Each Edge
This approach iterates through every connection in the network. For each connection, it is temporarily removed, and then the algorithm checks if the network remains connected. If the network becomes disconnected, the removed connection is identified as a critical connection.
**Time:** O(E * (V + E)), where V is the number of servers (`n`) and E is the number of connections. For each of the E edges, we build a new adjacency list (which takes O(V+E)) and then perform a DFS/BFS (which also takes O(V+E)). · **Space:** O(V + E). In each iteration of the main loop, we build an adjacency list which requires O(V+E) space. The recursion stack for DFS can also go up to O(V).
**Pros:** Simple to understand and implement.; Directly follows the definition of a critical connection, making the logic straightforward.
**Cons:** Highly inefficient due to its O(E * (V+E)) time complexity.; Rebuilds the graph and performs a full traversal for each edge, leading to a lot of redundant computation.; Will result in a "Time Limit Exceeded" error on large inputs as specified in the problem constraints.
### Explanation
The core idea is to simulate the removal of each edge one by one and test for graph connectivity.

First, we build an adjacency list representation of the graph from the input `connections`. We then loop through each edge `(u, v)` from the original `connections` list. Inside the loop, we create a temporary graph that excludes the current edge `(u, v)`. We then perform a graph traversal, such as Depth-First Search (DFS) or Breadth-First Search (BFS), starting from an arbitrary node (e.g., node 0). We keep a count of the nodes visited during the traversal. After the traversal is complete, if the count of visited nodes is less than the total number of nodes `n`, it implies that the graph is disconnected. In this case, the edge `(u, v)` is a critical connection, and we add it to our result list. This process is repeated for all edges.

```java
class Solution {
    public List<List<Integer>> criticalConnections(int n, List<List<Integer>> connections) {
        List<List<Integer>> critical = new ArrayList<>();
        
        for (int i = 0; i < connections.size(); i++) {
            // Build adjacency list for the graph without the i-th connection
            List<List<Integer>> adj = new ArrayList<>();
            for (int j = 0; j < n; j++) {
                adj.add(new ArrayList<>());
            }
            
            for (int j = 0; j < connections.size(); j++) {
                if (i == j) continue;
                List<Integer> edge = connections.get(j);
                adj.get(edge.get(0)).add(edge.get(1));
                adj.get(edge.get(1)).add(edge.get(0));
            }
            
            // Check for connectivity
            if (!isConnected(n, adj)) {
                critical.add(connections.get(i));
            }
        }
        return critical;
    }
    
    private boolean isConnected(int n, List<List<Integer>> adj) {
        boolean[] visited = new boolean[n];
        int[] count = {0};
        // Start DFS from an arbitrary node (e.g., 0)
        dfs(0, adj, visited, count);
        return count[0] == n;
    }
    
    private void dfs(int u, List<List<Integer>> adj, boolean[] visited, int[] count) {
        visited[u] = true;
        count[0]++;
        for (int v : adj.get(u)) {
            if (!visited[v]) {
                dfs(v, adj, visited, count);
            }
        }
    }
}
```
### Algorithm
- Initialize an empty list `critical_connections` to store the results.
- For each connection `(u, v)` in the input list `connections`:
  - Create a new graph by building an adjacency list from all connections *except* `(u, v)`.
  - Perform a graph traversal (e.g., DFS) starting from node 0 to count the number of reachable nodes.
  - If the number of reachable nodes is less than `n`, the graph is disconnected. Add the connection `(u, v)` to `critical_connections`.
- Return `critical_connections`.

## Tarjan's Bridge-Finding Algorithm
This is an efficient, single-pass algorithm that uses Depth-First Search (DFS) to find all bridges (critical connections) in a graph. It works by keeping track of the discovery time of each node and the lowest discovery time reachable from it, allowing it to identify bridges in linear time.
**Time:** O(V + E). The algorithm is based on a single DFS traversal. Every vertex and every edge is visited exactly once. · **Space:** O(V + E). This is for storing the adjacency list (O(V+E)), the `disc` and `low` arrays (O(V)), and the recursion stack for DFS (O(V) in the worst case).
**Pros:** Highly efficient, with linear time complexity.; Solves the problem in a single pass over the graph.; It's the standard and optimal algorithm for finding bridges in a graph.
**Cons:** More complex to understand and implement compared to the brute-force approach.; Requires a good understanding of Depth-First Search and its properties, specifically back-edges and DFS trees.
### Explanation
The algorithm is based on a single DFS traversal of the graph. During the traversal, we maintain two key pieces of information for each node `u`:
1.  `disc[u]`: The discovery time, which is the step/time when `u` is first visited.
2.  `low[u]`: The "low-link" value, which is the lowest discovery time reachable from `u` (including itself) by traversing zero or more tree edges in the DFS tree and at most one back-edge.

We initialize `disc` and `low` arrays with a sentinel value (like -1). We also need an adjacency list for the graph and a global timer. We start the DFS from an arbitrary node. Let's say our DFS function is `dfs(u, parent)`.

When we visit a node `u`:
- We set `disc[u]` and `low[u]` to the current `time`, and then increment `time`.
- We iterate through `u`'s neighbors `v`.
- If `v` is the `parent` that we came from, we skip it.
- If `v` has been visited (i.e., `disc[v]` is not -1), it means we've found a back-edge. A back-edge from `u` to an ancestor `v` provides an alternative path. We update `low[u] = min(low[u], disc[v])`.
- If `v` has not been visited, it's a new node in our DFS tree. We make a recursive call `dfs(v, u)`.
- After the recursive call for `v` returns, the `low[v]` value has been fully computed for the subtree rooted at `v`. We can use this to update `u`'s low-link value: `low[u] = min(low[u], low[v])`.
- Now, we check the bridge condition. The edge `(u, v)` is a bridge if the subtree rooted at `v` has no back-edge connection to `u` or any of its ancestors. This is true if `low[v] > disc[u]`. If this condition holds, we've found a critical connection and add `(u, v)` to our result list.

```java
import java.util.*;

class Solution {
    private int time = 0;
    private List<List<Integer>> adj;
    private int[] low;
    private int[] disc;
    private List<List<Integer>> bridges;

    public List<List<Integer>> criticalConnections(int n, List<List<Integer>> connections) {
        // Build adjacency list
        adj = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            adj.add(new ArrayList<>());
        }
        for (List<Integer> conn : connections) {
            int u = conn.get(0);
            int v = conn.get(1);
            adj.get(u).add(v);
            adj.get(v).add(u);
        }

        // Initialize arrays
        low = new int[n];
        disc = new int[n];
        Arrays.fill(disc, -1); // -1 indicates unvisited
        bridges = new ArrayList<>();

        // Start DFS from node 0 (since the graph is connected)
        // The parent of the starting node can be a sentinel value like -1
        dfs(0, -1);

        return bridges;
    }

    private void dfs(int u, int parent) {
        disc[u] = low[u] = time++;
        
        for (int v : adj.get(u)) {
            if (v == parent) {
                continue; // Skip the edge back to the parent
            }
            
            if (disc[v] != -1) { // v is a visited node (a back-edge)
                low[u] = Math.min(low[u], disc[v]);
            } else { // v is an unvisited node (a tree-edge)
                dfs(v, u);
                // After visiting v's subtree, update low[u]
                low[u] = Math.min(low[u], low[v]);
                
                // Check for bridge condition
                if (low[v] > disc[u]) {
                    bridges.add(Arrays.asList(u, v));
                }
            }
        }
    }
}
```
### Algorithm
- Build an adjacency list representation of the graph.
- Initialize `disc` and `low` arrays of size `n` with a sentinel value (e.g., -1).
- Initialize a global `time` counter to 0.
- Initialize an empty list `bridges` to store the results.
- Define a DFS function `dfs(u, parent)`.
- Inside `dfs(u, parent)`:
  - Set `disc[u] = low[u] = time++`.
  - For each neighbor `v` of `u`:
    - If `v` is `parent`, continue.
    - If `v` is visited (`disc[v] != -1`), update `low[u] = min(low[u], disc[v])`.
    - If `v` is not visited, recursively call `dfs(v, u)`. After the call returns, update `low[u] = min(low[u], low[v])`.
    - Check if `low[v] > disc[u]`. If true, the edge `(u, v)` is a bridge. Add it to the `bridges` list.
- Start the traversal by calling `dfs(0, -1)` (since the graph is connected).
- Return the `bridges` list.

# Solutions
### Java

```java
class Solution {
private
  int now;
private
  List<Integer>[] g;
private
  List<List<Integer>> ans = new ArrayList<>();
private
  int[] dfn;
private
  int[] low;
public
  List<List<Integer>> criticalConnections(int n,
                                          List<List<Integer>> connections) {
    g = new List[n];
    Arrays.setAll(g, k->new ArrayList<>());
    dfn = new int[n];
    low = new int[n];
    for (var e : connections) {
      int a = e.get(0), b = e.get(1);
      g[a].add(b);
      g[b].add(a);
    }
    tarjan(0, -1);
    return ans;
  }
private
  void tarjan(int a, int fa) {
    dfn[a] = low[a] = ++now;
    for (int b : g[a]) {
      if (b == fa) {
        continue;
      }
      if (dfn[b] == 0) {
        tarjan(b, a);
        low[a] = Math.min(low[a], low[b]);
        if (low[b] > dfn[a]) {
          ans.add(List.of(a, b));
        }
      } else {
        low[a] = Math.min(low[a], dfn[b]);
      }
    }
  }
}

```

### CPP

```cpp
class Solution {
public:
  vector<vector<int>> criticalConnections(int n,
                                          vector<vector<int>> &connections) {
    int now = 0;
    vector<int> dfn(n);
    vector<int> low(n);
    vector<int> g[n];
    for (auto &e : connections) {
      int a = e[0], b = e[1];
      g[a].push_back(b);
      g[b].push_back(a);
    }
    vector<vector<int>> ans;
    function<void(int, int)> tarjan = [&](int a, int fa) -> void {
      dfn[a] = low[a] = ++now;
      for (int b : g[a]) {
        if (b == fa) {
          continue;
        }
        if (!dfn[b]) {
          tarjan(b, a);
          low[a] = min(low[a], low[b]);
          if (low[b] > dfn[a]) {
            ans.push_back({a, b});
          }
        } else {
          low[a] = min(low[a], dfn[b]);
        }
      }
    };
    tarjan(0, -1);
    return ans;
  }
};

```

### Python

```python
class Solution:
    def criticalConnections(self, n: int, connections: List[List[int]]) -> List[List[int]]: def tarjan(a: int, fa: int): nonlocal now now += 1 dfn[a] = low[a] = now for b in g[a]: if b == fa: continue if not dfn[b]: tarjan(b, a) low[a] = min(low[a], low[b]) if low[b] > dfn[a]: ans . append([a, b]) else: low[a] = min(low[a], dfn[b]) g = [[] for _ in range(n)] for a, b in connections: g[a]. append(b) g[b]. append(a) dfn = [0] * n low = [0] * n now = 0 ans = [] tarjan(0, - 1) return ans

```