link
DFS with rank()1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51// import java.util.*;
class Solution {
static List<List<Integer>> criticalConnections(int n, List<List<Integer>> connections) {
List<Integer>[] graph = new ArrayList[n];
for (int i = 0; i < n; i++) {
graph[i] = new ArrayList<>();
}
for (List<Integer> oneConnection : connections) {
graph[oneConnection.get(0)].add(oneConnection.get(1));
graph[oneConnection.get(1)].add(oneConnection.get(0));
}
HashSet<List<Integer>> connectionsSet = new HashSet<>(connections);
int[] rank = new int[n];
Arrays.fill(rank, -2);
dfs(graph, 0, 0, rank, connectionsSet);
return new ArrayList<>(connectionsSet);
}
static int dfs(List<Integer>[] graph, int node, int depth, int[] rank, HashSet<List<Integer>> connectionsSet) {
if (rank[node] >= 0) {
return rank[node]; // already visited node. return its rank
}
rank[node] = depth;
int min_back_depth = depth; // can be Integer.MAX_VALUE also.
for (Integer neighbor : graph[node]) {
if (rank[neighbor] == depth - 1) { // ignore parent
continue; // that's why i didn't choose -1 as the special value, in case depth==0.
}
int back_depth = dfs(graph, neighbor, depth + 1, rank, connectionsSet);
if (back_depth <= depth) {
// to avoid the sorting just try to remove both combinations. of (x,y) and (y,x)
connectionsSet.remove(Arrays.asList(node, neighbor));
connectionsSet.remove(Arrays.asList(neighbor, node));
}
min_back_depth = Math.min(min_back_depth, back_depth);
}
return min_back_depth;
}
}
/*
public class MyClass {
public static void main(String[] args) {
int n=4;
List<List<Integer>> connections=new ArrayList<>();
connections.add(new ArrayList<>(Arrays.asList(0,1)));
connections.add(new ArrayList<>(Arrays.asList(1,2)));
connections.add(new ArrayList<>(Arrays.asList(2,0)));
connections.add(new ArrayList<>(Arrays.asList(1,3)));
System.out.println(Solution.criticalConnections(n, connections));
}
}*/
link1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26/*
class Solution {
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];
}
}*/