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;
    }
};
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
33
34
35
36
37
38
39

class Solution:
    def closestMeetingNode(self, p: List[int], x: int, y: int) -> int:
        n = len(p)
        d1 = [-1] * n
        d2 = [-1] * n 
        d1[x] = 0 
        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]
        
        # print(d1)
        # print(d2)
        res, id = -1, -1
        for 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), i
        
        return id
 
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

灵佬的代码：

最后一个循环的优化：

class Solution:
    def closestMeetingNode(self, edges: List[int], node1: int, node2: int) -> int:
        n, min_dis, ans = len(edges), len(edges), -1
        def calc_dis(x: int) -> List[int]:
            dis = [n] * n
            d = 0
            while x >= 0 and dis[x] == n:
                dis[x] = d
                d += 1
                x = edges[x]
            return dis
        for 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, i
        return 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）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21