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

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

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];
}