> For the complete documentation index, see [llms.txt](https://wentao-shao.gitbook.io/leetcode/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://wentao-shao.gitbook.io/leetcode/graph-search/1192.critical-connections-in-a-network.md).

# 1192.Critical-Connections-in-a-Network

## 1192. Critical Connections in a Network

## 题目地址

<https://leetcode.com/problems/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, b] represents a connection between servers a and b. Any server can reach any other server directly or indirectly through the network.

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

Return all critical connections in the network in any order.

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

Constraints:

1 <= n <= 10^5
n-1 <= connections.length <= 10^5
connections[i][0] != connections[i][1]
There are no repeated connections.
```

## 代码

### Approach 1: Tarjan

**An edge is a critical connection, if and only if it is not in a cycle.**

<https://zhuanlan.zhihu.com/p/101923309>

```java
class Solution {
    public List<List<Integer>> criticalConnections(int n, List<List<Integer>> connections) {
        int time = 0;
        int[] low = new int[n];
        int[] disc = new int[n];
        boolean[] visited = new boolean[n];
        List<List<Integer>> ans = new ArrayList<>();

              // 1. build adj
        List<Integer>[] adj = new ArrayList[n];
        for (int i = 0; i < n; i++) {
            adj[i] = new ArrayList<>();
        }
        for (List<Integer> node : connections) {
            adj[node.get(0)].add(node.get(1));
            adj[node.get(1)].add(node.get(0));
        }

          // 2. dfs
        dfs(0, -1, time, adj, low, disc, visited, ans);

        return ans;
    }

    private void dfs(int current , int parent, int time,  List<Integer>[] adj, int[] low, int[] disc, boolean[] visited, List<List<Integer>> ans) {
        time++;
        low[current] = time;
        disc[current] = time;
        visited[current] = true;

        for (int neighbor: adj[current]) {
            if (neighbor == parent) continue;

            if (visited[neighbor] == false) {
                dfs(neighbor, current, time, adj, low, disc, visited, ans);
                low[current] = Math.min(low[current], low[neighbor]);

                 // If the lowest vertex reachable from subtree 
                // under neighbor is below current in DFS tree, then current-neighbor is a bridge 
                if (low[neighbor] > disc[current]) {
                    ans.add(Arrays.asList(current, neighbor));
                }

            } else {
                low[current] = Math.min(low[current], disc[neighbor]); // ?? => low[neighbor]
            }
        }
    }
}
```

### #2

```java
private List<List<Integer>> ans = new ArrayList<>();
public List<List<Integer>> criticalConnections(int n, List<List<Integer>> connections) {
  Map<Integer, List<Integer>> graph = new HashMap<>();
  for (List<Integer> c: connections) {
    graph.computeIfAbsent(c.get(0), (k -> new ArrayList<Integer>())).add(c.get(1));
    graph.computeIfAbsent(c.get(1), (k -> new ArrayList<Integer>())).add(c.get(0));
  }
  int[] timestamps = new int[n];
  dfs(graph, 0, 0, 1, timestamps);
  return ans;
}

private int dfs(Map<Integer, List<Integer>> graph, int curr, int parent, int currTimestamp, int[] timestamps) {
  timestamps[curr] = currTimestamp;
  for (int nextNode : graph.getOrDefault(curr, new ArrayList<Integer>())) {
    if (nextNode == parent) continue;

    if (timestamps[nextNode] > 0) {
      timestamps[curr] = Math.min(timestamps[curr], timestamps[nextNode]);
    } else {
      timestamps[curr] = Math.min(timestamps[curr], 
                                  dfs(graph, nextNode, curr, currTimestamp + 1, timestamps));
    }

    if (currTimestamp < timestamps[nextNode]) {
      ans.add(Arrays.asList(curr, nextNode)); 
    }
  }
  return timestamps[curr];
}
```


---

# Agent Instructions
This documentation is published with GitBook. GitBook is the documentation platform designed so that both humans and AI agents can read, navigate, and reason over technical content effectively. Learn more at gitbook.com.

## Querying This Documentation
If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter, and the optional `goal` query parameter:

```
GET https://wentao-shao.gitbook.io/leetcode/graph-search/1192.critical-connections-in-a-network.md?ask=<question>&goal=<endgoal>
```

`ask` is the immediate question: it should be specific, self-contained, and written in natural language.
`goal` is optional and describes the broader end goal you are ultimately trying to accomplish on behalf of the user. GitBook uses it to tailor the answer towards what is most useful for that goal.

The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.