LeetCode 2359. 找到离给定两个节点最近的节点 基环树

基环树

1. 对于有向图来说：基环树就是一个环上挂了一堆树，每个节点只有一个出边，可能有环
2. 对于无向图来说：n个点n条边的联通，一定是一个基环树
   

题目描述

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

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

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

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

注意 edges 可能包含环。

示例 1：

输入：edges = [2,2,3,-1], node1 = 0, node2 = 1
输出：2
解释：从节点 0 到节点 2 的距离为 1 ，从节点 1 到节点 2 的距离为 1 。
两个距离的较大值为 1 。我们无法得到一个比 1 更小的较大值，所以我们返回节点 2 。
示例 2：

输入：edges = [1,2,-1], node1 = 0, node2 = 2
输出：2
解释：节点 0 到节点 2 的距离为 2 ，节点 2 到它自己的距离为 0 。
两个距离的较大值为 2 。我们无法得到一个比 2 更小的较大值，所以我们返回节点 2 。

提示：

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
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
数据量10的五次方，要控制在nlogn以内。
思路很简单，就是求出来每个点到两个起点的距离，然后再遍历每个点，在维护距离最大值的同时，维护一个id的最小值。

求每个点到起点的最短距离，由于每个边权重一样，直接BFS就可以，但是由于是基环树，起点到每个点的路径是唯一的，所以也不用BFS这么麻烦了，直接沿着临边遍历即可。

class Solution {
public:int closestMeetingNode(vector<int>& p, int x, int y) {int n = p.size();vector<int> d1(n, -1), d2(n, -1); // 存每个点到起点的距离// 初始化d1[x] = d2[y] = 0;while(p[x] != -1){   // 如果有环，则退出if(d1[p[x]] != -1) break;d1[p[x]] = d1[x] + 1;x = p[x];}while(p[y] != -1){if(d2[p[y]] != -1) break;d2[p[y]] = d2[y] + 1;y = p[y];}// 遍历所有节点int res = -1, id = -1;for(int i = 0; i < n; i ++){int a = d1[i], b = d2[i];if(a != -1 && b != -1){if(res == -1 || res > max(a, b)){res = max(a, b);id = i;}}}return id;}
};

class Solution:def closestMeetingNode(self, p: List[int], x: int, y: int) -> int:n = len(p)d1 = [-1] * nd2 = [-1] * n d1[x] = 0 d2[y] = 0while p[x] != -1:if d1[p[x]] != -1:breakd1[p[x]] = d1[x] + 1x = p[x]while p[y] != -1:if d2[p[y]] != -1:breakd2[p[y]] = d2[y] + 1y = p[y]# print(d1)# print(d2)res, id = -1, -1for i in range(n):a, b = d1[i], d2[i]if a != -1 and b != -1:if res == -1 or res > max(a, b):res, id = max(a, b), ireturn id

灵佬的代码：

最后一个循环的优化：

class Solution:def closestMeetingNode(self, edges: List[int], node1: int, node2: int) -> int:n, min_dis, ans = len(edges), len(edges), -1def calc_dis(x: int) -> List[int]:dis = [n] * nd = 0while x >= 0 and dis[x] == n:dis[x] = dd += 1x = edges[x]return disfor i, d1, d2 in zip(range(n), calc_dis(node1), calc_dis(node2)):d = max(d1, d2)if d < min_dis:min_dis, ans = d, ireturn ans作者：endlesscheng
链接：https://leetcode.cn/problems/find-closest-node-to-given-two-nodes/solution/ji-suan-dao-mei-ge-dian-de-ju-chi-python-gr2u/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。