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
| class Solution {
public int closestMeetingNode(int[] edges, int node1, int node2) {
Map<Integer, Integer> reachableNode1 = new HashMap<>();
Map<Integer, Integer> reachableNode2 = new HashMap<>();
dfs(reachableNode1, node1, new boolean[edges.length], edges, 0);
dfs(reachableNode2, node2, new boolean[edges.length], edges, 0);
int distance = Integer.MAX_VALUE, targetNode = -1;
for (Map.Entry<Integer, Integer> entry : reachableNode1.entrySet()) {
int reachable1 = entry.getKey(), steps1 = entry.getValue();
if (reachableNode2.containsKey(reachable1)) {
int steps2 = reachableNode2.get(reachable1);
int currMax = Math.max(steps1, steps2);
if (currMax < distance || (currMax == distance && reachable1 < targetNode)) {
distance = currMax;
targetNode = reachable1;
}
}
}
return targetNode;
}
private void dfs(Map<Integer, Integer> nodeDistance, int currNode, boolean[] visited, int[] edges, int steps) {
visited[currNode] = true;
nodeDistance.put(currNode, steps);
int nextNode = edges[currNode];
if (nextNode != -1 && !visited[nextNode]) {
dfs(nodeDistance, nextNode, visited, edges, steps + 1);
}
}
}
|
