给出一幅有向图的边的连接情况（edges数组包含n个值，edges[i]不等于-1表示存在从i到edges[i]的边），节点编号o~n-1，给出node1，node2两个节点问是否存在一个节点j，使得从node1到j和从node2到j的两个距离中的较大值最小，输出这个节点值，如果不存在，输出-1
DFS分别预处理从node1和node2到每个其他节点的距离，因为原图有环，注意是否已经访问过（看dis数组是否已经更新），然后枚举所有节点，找出是否存在所求节点j
1 #2359
2 #Runtime: 1986 ms (Beats 26.67%)
3 #Memory: 115 MB (Beats 13.33%)
4
5 class Solution(object):
6 def closestMeetingNode(self, edges, node1, node2):
7 """
8 :type edges: List[int]
9 :type node1: int
10 :type node2: int
11 :rtype: int
12 """
13
14 def DFS(r, d, dis):
15 if r == -1 or dis[r] != -1:
16 return
17 dis[r] = d
18 DFS(edges[r], d + 1, dis)
19
20 n = len(edges)
21 dis1, dis2 = [-1] * n, [-1] * n
22 DFS(node1, 0, dis1)
23 DFS(node2, 0, dis2)
24 min_dis = 100001
25 ans = -1
26 for i in range(n):
27 if min(dis1[i], dis2[i]) >= 0 and max(dis1[i], dis2[i]) < min_dis:
28 min_dis = max(dis1[i], dis2[i])
29 ans = i
30 return ans