0DFS Medium LeetCode6134. Find the closest node to the given two nodes

6134. Find the closest node to the given two nodes

描述

给你一个 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

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

分析

可达性分析
Node1 和node2分别遍历一次,Record the distance to each node,Then iterate over each node,在node1和node2Select from the nodes that can be reachednode1和node2The smallest node that reaches the larger value of this node.
Note the distance from1开始这样node1,node2The distance will not be0,It is convenient to exclude which nodes cannot be reached by two nodes.

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;
    }
}