0DFS中等 LeetCode6134. 找到离给定两个节点最近的节点

6134. 找到离给定两个节点最近的节点

描述

给你一个 n 个节点的 有向图 ，节点编号为 0 到 n - 1 ，每个节点 至多 有一条出边。

有向图用大小为 n 下标从 0 开始的数组 edges 表示，表示节点 i 有一条有向边指向 edges[i] 。如果节点 i 没有出边，那么 edges[i] == -1 。

同时给你两个节点 node1 和 node2 。

请你返回一个从 node1 和 node2 都能到达节点的编号，使节点 node1 和节点 node2 到这个节点的距离 较大值最小化。如果有多个答案，请返回 最小 的节点编号。如果答案不存在，返回 -1 。

注意 edges 可能包含环。

提示：

n == edges.length
2 <= n <= 105
-1 <= edges[i] < n
edges[i] != i
0 <= node1, node2 < n
1
2
3
4
5

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/find-closest-node-to-given-two-nodes
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

分析

可达性分析
Node1 和node2分别遍历一次，记录到每个结点的距离，然后遍历每个结点，在node1和node2都能到达的结点中选择node1和node2到达该结点较大值的最小的结点。
注意距离从1开始这样node1,node2的距离不会是0，方便排除掉哪些两个结点不能达到的结点。

class Solution {
    public int closestMeetingNode(int[] edges, int node1, int node2) {
        int n = edges.length;
        int[] len = new int[n];
        int[] len2 = new int[n];
        int i = node1, j = node2;
        int l1 = 1;
        int l2 = 1;
        while (i != -1 && len[i] == 0) {
            len[i] = l1;
            l1++;
            i = edges[i];
        }
        int ans = -1;
        int max = n+2;
        while (j != -1 && len2[j] == 0) {
            len2[j] = l2;
            l2++;
            j = edges[j];
        }
        for (int k = 0; k < n; k++) {
            if (len[k] != 0 && len2[k] != 0) {
                int tmp = Math.max(len[k],len2[k]);
                if (max > tmp) {
                    max = tmp;
                    ans = k;
                }
            }
        }
        return ans;
    }
}
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