給出一幅有向圖的邊的連接情況（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