题目

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:

image.png

  1. Input: n = 4, connections = [[0,1],[1,2],[2,0],[1,3]]
  2. Output: [[1,3]]
  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.

题意

在无向图中找到所有的边，使得删去该边后，存在两结点无法互相到达。

思路

tarjan算法，求所有的”桥”。

代码实现

Java

  1. class Solution {
  2.     private Map<Integer, List<Integer>> graph;
  3.     private boolean[] visited;
  4.     private int[] dfn;
  5.     private int[] low;
  6.     private int num;
  8.     public List<List<Integer>> criticalConnections(int n, List<List<Integer>> connections) {
  9.         graph = new HashMap<>();
  10.         visited = new boolean[n];
  11.         dfn = new int[n];
  12.         low = new int[n];
  13.         num = 0;
  15.         List<List<Integer>> ans = new ArrayList<>();
  17.         for (List<Integer> edge : connections) {
  18.             int a = edge.get(0);
  19.             int b = edge.get(1);
  20.             graph.putIfAbsent(a, new ArrayList<>());
  21.             graph.putIfAbsent(b, new ArrayList<>());
  22.             graph.get(a).add(b);
  23.             graph.get(b).add(a);
  24.         }
  26.         tarjan(0, -1, ans);
  28.         return ans;
  29.     }
  31.     private void tarjan(int cur, int parent, List<List<Integer>> ans) {
  32.         visited[cur] = true;
  33.         dfn[cur] = num++;
  34.         low[cur] = dfn[cur];
  36.         for (int next : graph.get(cur)) {
  37.             if (!visited[next]) {
  38.                 tarjan(next, cur, ans);
  39.                 low[cur] = Math.min(low[cur], low[next]);
  40.                   // 满足条件时说明删去改变子结点和父结点将不在同一个连通分量中
  41.                 if (low[next] > dfn[cur]) ans.add(Arrays.asList(cur, next));
  42.             } else if (next != parent) {            // 必须排除与父结点的边
  43.                 low[cur] = Math.min(low[cur], dfn[next]);
  44.             }
  45.         }
  46.     }
  47. }