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

难度: Medium

给你一个 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 <= 10⁵
-1 <= edges[i] < n
edges[i] != i
0 <= node1, node2 < n

Submission

运行时间: 64 ms

内存: 27.8 MB

class Solution:
    def closestMeetingNode(self, edges: List[int], node1: int, node2: int) -> int:
        flag_1 = [False] * len(edges)
        flag_2 = [False] * len(edges)
        flag_1[node1], flag_2[node2] = True, True
        cur_1, cur_2 = node1, node2
        while True:
            judge_1, judge_2 = False, False
            if flag_1[cur_2] and flag_2[cur_1]:
                return min(cur_1, cur_2)
            if flag_2[cur_1]:
                return cur_1
            if flag_1[cur_2]:
                return cur_2
            if edges[cur_1] != -1:
                if not flag_1[edges[cur_1]]:
                    cur_1 = edges[cur_1]
                    flag_1[cur_1] = True
                    judge_1 = True
            if edges[cur_2] != -1:
                if not flag_2[edges[cur_2]]:
                    cur_2 = edges[cur_2]
                    flag_2[cur_2] = True
                    judge_2 = True
            if not judge_1 and not judge_2:
                return -1

Explain

该题解采用的是同时从两个节点开始追踪路径的策略。首先，创建两个布尔数组flag_1和flag_2来标记从node1和node2出发访问过的节点。接着，从两个节点同时开始沿着有向图的边走，直到两者相遇或到达终点。过程中检查对方是否已经访问过当前节点，若是，则返回当前节点，因为这意味着找到了一个共同可达节点。如果在某一步中，一个节点无法再前进（即该节点没有出边或到达了先前访问过的节点），则停止并返回-1，表示不存在这样的节点。这种方法利用了双指针的思想，同时追踪两个节点的路径，直到它们相遇。

时间复杂度: O(n)

空间复杂度: O(n)

class Solution:
    def closestMeetingNode(self, edges: List[int], node1: int, node2: int) -> int:
        flag_1 = [False] * len(edges)  # 从node1出发访问过的节点标记
        flag_2 = [False] * len(edges)  # 从node2出发访问过的节点标记
        flag_1[node1], flag_2[node2] = True, True  # 标记起始节点
        cur_1, cur_2 = node1, node2  # 初始化当前节点
        while True:
            judge_1, judge_2 = False, False  # 判断两个节点是否可以继续前进
            if flag_1[cur_2] and flag_2[cur_1]:
                return min(cur_1, cur_2)  # 如果两个节点同时访问对方的位置，则返回较小的节点编号
            if flag_2[cur_1]:
                return cur_1  # 如果node2已经访问过node1的当前位置
            if flag_1[cur_2]:
                return cur_2  # 如果node1已经访问过node2的当前位置
            if edges[cur_1] != -1:
                if not flag_1[edges[cur_1]]:
                    cur_1 = edges[cur_1]  # 更新node1的当前位置
                    flag_1[cur_1] = True
                    judge_1 = True
            if edges[cur_2] != -1:
                if not flag_2[edges[cur_2]]:
                    cur_2 = edges[cur_2]  # 更新node2的当前位置
                    flag_2[cur_2] = True
                    judge_2 = True
            if not judge_1 and not judge_2:
                return -1  # 如果两个节点都不能前进，返回-1

Explore

题解中的策略确实考虑到了环形结构的存在。由于使用了两个布尔数组flag_1和flag_2来标记每个节点是否被访问过，这样一来，即使图中存在环，一旦某个节点再次被访问时，算法将不会进入该节点，从而避免了无限循环。这种方法可以有效地处理环形结构，确保算法总能在有限步骤内返回结果或者判断不存在共同节点。

题解中直接返回-1的情况是基于算法的逻辑，当两个节点都无法前进时（即没有未访问的出边），说明已经探索了所有可能的路径。由于从两个节点出发的路径都已经追踪完毕且没有交点，因此可以确定不存在其他未被考虑到的节点作为合适的最近共同节点。这种情况下，返回-1表示在现有图结构中，没有共同的可达节点。

这种方法在有向图中基本上是有效的，尤其是在本题的上下文中，因为问题的设置是找到两个节点的最近共同节点。如果一个节点已经被对方访问过，那么这意味着从两个起始节点都可以到达这个节点。然而，需要注意的是，这种方法假设了节点的可达性是对称的，即如果从A可达B，则从B也可以回到A。在某些特定的有向图结构中（如不对称的），这个假设可能不成立。但对于本题的目的而言，这种方法是适用的。

题解中的假设确实限制了算法的通用性，因为它只适用于每个节点至多有一条出边的场景。如果在一个更一般的图中，节点可能有多条出边，算法需要调整以处理这种复杂性。一种可能的调整是使用广度优先搜索（BFS）。对每个节点，我们可以维护一个队列来探索所有可能的出边，同时还需要标记访问过的节点以避免重复访问。这种方法能够在更一般的图结构中找到最近的共同可达节点。