颜色交替的最短路径

难度: Medium

给定一个整数 n，即有向图中的节点数，其中节点标记为 0 到 n - 1。图中的每条边为红色或者蓝色，并且可能存在自环或平行边。

给定两个数组 redEdges 和 blueEdges，其中：

redEdges[i] = [a_i, b_i] 表示图中存在一条从节点 a_i 到节点 b_i 的红色有向边，
blueEdges[j] = [u_j, v_j] 表示图中存在一条从节点 u_j 到节点 v_j 的蓝色有向边。

返回长度为 n 的数组 answer，其中 answer[X] 是从节点 0 到节点 X 的红色边和蓝色边交替出现的最短路径的长度。如果不存在这样的路径，那么 answer[x] = -1。

示例 1：

输入：n = 3, red_edges = [[0,1],[1,2]], blue_edges = []
输出：[0,1,-1]

示例 2：

输入：n = 3, red_edges = [[0,1]], blue_edges = [[2,1]]
输出：[0,1,-1]

提示：

1 <= n <= 100
0 <= redEdges.length, blueEdges.length <= 400
redEdges[i].length == blueEdges[j].length == 2
0 <= a_i, b_i, u_j, v_j < n

Submission

运行时间: 28 ms

内存: 16.2 MB

class Solution:
    def shortestAlternatingPaths(self, n: int, redEdges: List[List[int]], blueEdges: List[List[int]]) -> List[int]:
        gr = {i: [] for i in range(n)}
        gb = {i: [] for i in range(n)}
        for u, v in redEdges:
            gr[u].append(v)
        for u, v in blueEdges:
            gb[u].append(v)
        ans = [-1] * n
        from collections import deque
        q = deque([(0, 0, 1), (0, 0, 0)])
        vis = set()
        while q:
            u, d, op = q.popleft()
            if (u, op) in vis:
                continue
            vis.add((u, op))
            if ans[u] == -1 or d < ans[u]:
                ans[u] = d
            if op == 1:
                for v in gr[u]:
                    q.append((v, d + 1, 0))
            else:
                for v in gb[u]:
                    q.append((v, d + 1, 1))

        return ans

Explain

该题解使用了广度优先搜索（BFS）的方法来寻找从节点0到其他节点的最短交替路径。首先，将红色和蓝色边分别存储在两个字典中，以便于后续查找。然后，使用一个队列来进行BFS，队列中的元素是一个三元组(u, d, op)，其中u表示当前节点，d表示当前路径长度，op表示下一步应该走的边的颜色（1代表红色，0代表蓝色）。同时，使用一个集合vis来记录已经访问过的节点和颜色的组合，避免重复访问。在BFS的过程中，根据当前节点和边的颜色，将相邻的节点加入队列中，并更新最短路径长度。

时间复杂度: O(V + E)

空间复杂度: O(V + E)

class Solution:
    def shortestAlternatingPaths(self, n: int, redEdges: List[List[int]], blueEdges: List[List[int]]) -> List[int]:
        gr = {i: [] for i in range(n)}  # 存储红色边
        gb = {i: [] for i in range(n)}  # 存储蓝色边
        for u, v in redEdges:
            gr[u].append(v)
        for u, v in blueEdges:
            gb[u].append(v)
        ans = [-1] * n  # 初始化答案数组
        from collections import deque
        q = deque([(0, 0, 1), (0, 0, 0)])  # 初始化队列，包括起点、距离和下一步的颜色
        vis = set()  # 记录已访问的节点和颜色
        while q:
            u, d, op = q.popleft()
            if (u, op) in vis:
                continue
            vis.add((u, op))
            if ans[u] == -1 or d < ans[u]:
                ans[u] = d
            if op == 1:
                for v in gr[u]:
                    q.append((v, d + 1, 0))
            else:
                for v in gb[u]:
                    q.append((v, d + 1, 1))

        return ans

Explore

在该题目中，我们需要找到从节点0到其他所有节点的最短交替路径。由于路径可以从任意颜色的边开始，因此在初始化队列时，从节点0开始并为红色和蓝色边各自添加一个三元组是为了确保考虑从节点0出发，首先通过红色边或蓝色边的所有可能的路径。这种方法确保了搜索过程能全面覆盖所有从节点0出发的交替颜色路径。

在这个问题中，路径需要交替颜色，即从一个红色边到达的节点下一步必须通过蓝色边离开，反之亦然。因此，仅记录节点编号不足以确保路径的颜色交替。通过记录(node, color)组合，我们可以确保每次访问节点时都是从不同颜色的边到达的，这样就可以正确地遵循交替路径的要求。

在广度优先搜索中，自环和平行边可能导致重复访问和无限循环。为了避免这种情况，我们使用vis集合来记录已访问的(node, color)组合。每次访问一个节点前，检查该节点和颜色组合是否已在vis集合中。如果已存在，则跳过该组合的进一步处理。这种方法可以有效地避免因自环或平行边导致的无限循环，同时确保每个节点的每种颜色的访问只发生一次。

在这个问题中，数组ans用于记录从节点0到每个其他节点的最短路径长度。初始化为-1的原因是-1可以明确表示从节点0到某个节点不存在任何有效的交替颜色路径。这是一个常用的技巧，用于区分尚未找到路径的节点（值为-1）和已找到路径的节点（值为非负整数）。这样，最终结果直接反映哪些节点是可达的，并给出相应的最短路径长度。