Critical Connections in a Network LeetCode solution in Java

1
class Solution {
2
  // We record the timestamp that we visit each node. For each node, we check every neighbor except
3
  // its parent and return a smallest timestamp in all its neighbors. If this timestamp is strictly
4
  // less than the node's timestamp, we know that this node is somehow in a cycle. Otherwise, this
5
  // edge from the parent to this node is a critical connection
6
  public List<List<Integer>> criticalConnections(int n, List<List<Integer>> connections) {
7
    List<Integer>[] graph = new ArrayList[n];
8
    for (int i = 0; i < n; i++) graph[i] = new ArrayList<>();
9

10
    for (List<Integer> oneConnection : connections) {
11
      graph[oneConnection.get(0)].add(oneConnection.get(1));
12
      graph[oneConnection.get(1)].add(oneConnection.get(0));
13
    }
14
    int timer[] = new int[1];
15
    List<List<Integer>> results = new ArrayList<>();
16
    boolean[] visited = new boolean[n];
17
    int[] timeStampAtThatNode = new int[n];
18
    criticalConnectionsUtil(graph, -1, 0, timer, visited, results, timeStampAtThatNode);
19
    return results;
20
  }
21

22
  public void criticalConnectionsUtil(
23
      List<Integer>[] graph,
24
      int parent,
25
      int node,
26
      int timer[],
27
      boolean[] visited,
28
      List<List<Integer>> results,
29
      int[] timeStampAtThatNode) {
30
    visited[node] = true;
31
    timeStampAtThatNode[node] = timer[0]++;
32
    int currentTimeStamp = timeStampAtThatNode[node];
33

34
    for (int oneNeighbour : graph[node]) {
35
      if (oneNeighbour == parent) continue;
36
      if (!visited[oneNeighbour])
37
        criticalConnectionsUtil(
38
            graph, node, oneNeighbour, timer, visited, results, timeStampAtThatNode);
39
      timeStampAtThatNode[node] =
40
          Math.min(timeStampAtThatNode[node], timeStampAtThatNode[oneNeighbour]);
41
      if (currentTimeStamp < timeStampAtThatNode[oneNeighbour])
42
        results.add(Arrays.asList(node, oneNeighbour));
43
    }
44
  }
45
}