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.
Example 1:
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^5n-1 <= connections.length <= 10^5connections[i][0] != connections[i][1]
class Solution { public List<List<Integer>> criticalConnections(int n, List<List<Integer>> connections) { List<List<Integer>> res = new ArrayList<>(); List<Integer>[] graph = new ArrayList[n]; int[] jumps = new int[n]; Arrays.fill(jumps, -1); // build bidirectional graph for (int i = 0; i < n; i++) { graph[i] = new ArrayList<>(); } for (List<Integer> list : connections) { int from = list.get(0); int to = list.get(1); graph[from].add(to); graph[to].add(from); } dfs(0, -1, 0, res, graph, jumps); return res; } private int dfs(int cur, int parent, int level, List<List<Integer>> res, List<Integer>[] graph, int[] jumps) { jumps[cur] = level + 1; for (int child : graph[cur]) { // child == parent instead of cur if (child == parent) { continue; } else if (jumps[child] == -1) { jumps[cur] = Math.min(jumps[cur], dfs(child, cur, level + 1, res, graph, jumps)); } else { jumps[cur] = Math.min(jumps[cur], jumps[child]); } } if (jumps[cur] == level + 1 && cur != 0) { res.add(Arrays.asList(parent, cur)); } return jumps[cur]; } }
[LC] 1192. Critical Connections in a Network
原文：https://www.cnblogs.com/xuanlu/p/12635500.html