Medium
题目描述
给你一个整数 n，表示一个有向图中节点的数目，节点编号为 0 到 n - 1。图中的每条边都是红色或者蓝色的，且可能存在自环或平行边。
给你两个数组 redEdges 和 blueEdges，其中：
redEdges[i] = [ai, bi]表示图中存在一条从节点ai到节点bi的红色有向边blueEdges[j] = [uj, vj]表示图中存在一条从节点uj到节点vj的蓝色有向边
返回长度为 n 的数组 answer，其中 answer[x] 是从节点 0 到节点 x 的最短路径的长度，且路径上的边的颜色必须交替出现。如果不存在这样的路径，则用 -1 作为答案。
示例 1：
输入：n = 3, redEdges = [[0,1],[1,2]], blueEdges = []
输出：[0,1,-1]
示例 2：
输入：n = 3, redEdges = [[0,1]], blueEdges = [[2,1]]
输出：[0,1,-1]
提示：
1 <= n <= 1000 <= redEdges.length, blueEdges.length <= 400redEdges[i].length == blueEdges[j].length == 20 <= ai, bi, uj, vj < n
解题思路
这是一个带有约束条件的最短路径问题，约束是路径上的边颜色必须交替出现。
核心思路： 将问题转换为在扩展图上的最短路径问题。我们可以将每个节点分成两个状态：
(node, RED)：到达该节点时最后一条边是红色(node, BLUE)：到达该节点时最后一条边是蓝色
算法步骤：
- 构建红色和蓝色的邻接表
- 使用BFS从起点0开始搜索，初始状态包含
(0, RED)和(0, BLUE)两种可能 - 对于每个状态
(node, color)，只能通过与当前颜色不同的边进行扩展 - 使用访问数组避免重复访问同一状态
- 记录到达每个节点的最短距离
时间复杂度分析：
- 每个节点最多访问2次（红色状态和蓝色状态各一次）
- 总的状态数为
O(n)，每条边最多被处理一次 - 时间复杂度：
O(n + redEdges.length + blueEdges.length)
这种方法确保了找到的路径满足颜色交替的约束，且是最短的。
代码实现
class Solution {
public:
vector<int> shortestAlternatingPaths(int n, vector<vector<int>>& redEdges, vector<vector<int>>& blueEdges) {
// 构建邻接表
vector<vector<int>> redGraph(n), blueGraph(n);
for (auto& edge : redEdges) {
redGraph[edge[0]].push_back(edge[1]);
}
for (auto& edge : blueEdges) {
blueGraph[edge[0]].push_back(edge[1]);
}
vector<int> result(n, -1);
// visited[node][color] - color: 0=red, 1=blue
vector<vector<bool>> visited(n, vector<bool>(2, false));
// BFS: {node, color, distance}
queue<tuple<int, int, int>> q;
q.push({0, 0, 0}); // start with red
q.push({0, 1, 0}); // start with blue
visited[0][0] = visited[0][1] = true;
result[0] = 0;
while (!q.empty()) {
auto [node, color, dist] = q.front();
q.pop();
// Choose next edges with opposite color
vector<vector<int>>& graph = (color == 0) ? blueGraph : redGraph;
int nextColor = 1 - color;
for (int next : graph[node]) {
if (!visited[next][nextColor]) {
visited[next][nextColor] = true;
if (result[next] == -1) {
result[next] = dist + 1;
}
q.push({next, nextColor, dist + 1});
}
}
}
return result;
}
};
class Solution:
def shortestAlternatingPaths(self, n: int, redEdges: List[List[int]], blueEdges: List[List[int]]) -> List[int]:
from collections import defaultdict, deque
# 构建邻接表
red_graph = defaultdict(list)
blue_graph = defaultdict(list)
for a, b in redEdges:
red_graph[a].append(b)
for u, v in blueEdges:
blue_graph[u].append(v)
result = [-1] * n
# visited[node][color] - color: 0=red, 1=blue
visited = [[False, False] for _ in range(n)]
# BFS: (node, color, distance)
queue = deque([(0, 0, 0), (0, 1, 0)]) # start with both colors
visited[0][0] = visited[0][1] = True
result[0] = 0
while queue:
node, color, dist = queue.popleft()
# Choose next edges with opposite color
graph = blue_graph if color == 0 else red_graph
next_color = 1 - color
for next_node in graph[node]:
if not visited[next_node][next_color]:
visited[next_node][next_color] = True
if result[next_node] == -1:
result[next_node] = dist + 1
queue.append((next_node, next_color, dist + 1))
return result
public class Solution {
public int[] ShortestAlternatingPaths(int n, int[][] redEdges, int[][] blueEdges) {
// 构建邻接表
List<int>[] redGraph = new List<int>[n];
List<int>[] blueGraph = new List<int>[n];
for (int i = 0; i < n; i++) {
redGraph[i] = new List<int>();
blueGraph[i] = new List<int>();
}
foreach (var edge in redEdges) {
redGraph[edge[0]].Add(edge[1]);
}
foreach (var edge in blueEdges) {
blueGraph[edge[0]].Add(edge[1]);
}
int[] result = new int[n];
Array.Fill(result, -1);
// visited[node, color] - color: 0=red, 1=blue
bool[,] visited = new bool[n, 2];
// BFS: (node, color, distance)
Queue<(int node, int color, int dist)> queue = new Queue<(int, int, int)>();
queue.Enqueue((0, 0, 0)); // start with red
queue.Enqueue((0, 1, 0)); // start with blue
visited[0, 0] = visited[0, 1] = true;
result[0] = 0;
while (queue.Count > 0) {
var (node, color, dist) = queue.Dequeue();
// Choose next edges with opposite color
List<int>[] graph = (color == 0) ? blueGraph : redGraph;
int nextColor = 1 - color;
foreach (int next in graph[node]) {
if (!visited[next, nextColor]) {
visited[next, nextColor] = true;
if (result[next] == -1) {
result[next] = dist + 1;
}
queue.Enqueue((next, nextColor, dist + 1));
}
}
}
return result;
}
}
var shortestAlternatingPaths = function(n, redEdges, blueEdges) {
const redGraph = Array(n).fill().map(() => []);
const blueGraph = Array(n).fill().map(() => []);
for (const [a, b] of redEdges) {
redGraph[a].push(b);
}
for (const [u, v] of blueEdges) {
blueGraph[u].push(v);
}
const result = Array(n).fill(-1);
result[0] = 0;
const queue = [[0, 0, 0], [0, 0, 1]]; // [node, distance, lastColor (0=red, 1=blue)]
const visited = Array(n).fill().map(() => [false, false]);
while (queue.length > 0) {
const [node, dist, lastColor] = queue.shift();
if (visited[node][lastColor]) continue;
visited[node][lastColor] = true;
if (result[node] === -1) {
result[node] = dist;
}
if (lastColor === 0) {
for (const neighbor of blueGraph[node]) {
if (!visited[neighbor][1]) {
queue.push([neighbor, dist + 1, 1]);
}
}
} else {
for (const neighbor of redGraph[node]) {
if (!visited[neighbor][0]) {
queue.push([neighbor, dist + 1, 0]);
}
}
}
}
return result;
};
复杂度分析
| 复杂度类型 | 分析 |
|---|---|
| 时间复杂度 | O(n + E)，其中 E 为边的总数。每个节点最多访问2次（红蓝状态各一次），每条边最多处理一次 |
| 空间复杂度 | O(n + E)，用于存储邻接表、访问数组和BFS队列 |