from collections import deque, defaultdict
def shortestAlternatingPaths(n, redEdges, blueEdges):
graph = [defaultdict(list) for _ in range(2)] # 0: red, 1: blue
for u, v in redEdges:
graph[0][u].append(v)
for u, v in blueEdges:
graph[1][u].append(v)
res = [-1] * n
visited = [[False] * n for _ in range(2)] # visited[color][node]
queue = deque()
queue.append((0, 0, -1)) # (node, steps, prev_color), -1 means start
while queue:
node, steps, prev_color = queue.popleft()
if res[node] == -1:
res[node] = steps
# Try both colors, but must alternate
for color in [0, 1]:
if color != prev_color:
for nei in graph[color][node]:
if not visited[color][nei]:
visited[color][nei] = True
queue.append((nei, steps + 1, color))
return res
#include <vector>
#include <queue>
#include <unordered_map>
using namespace std;
vector<int> shortestAlternatingPaths(int n, vector<vector<int>>& redEdges, vector<vector<int>>& blueEdges) {
vector<unordered_map<int, vector<int>>> graph(2); // 0: red, 1: blue
for (auto& e : redEdges) graph[0][e[0]].push_back(e[1]);
for (auto& e : blueEdges) graph[1][e[0]].push_back(e[1]);
vector<int> res(n, -1);
vector<vector<bool>> visited(2, vector<bool>(n, false));
queue<tuple<int, int, int>> q; // node, steps, prev_color
q.push({0, 0, -1});
while (!q.empty()) {
auto [node, steps, prev_color] = q.front(); q.pop();
if (res[node] == -1) res[node] = steps;
for (int color = 0; color < 2; ++color) {
if (color != prev_color) {
for (int nei : graph[color][node]) {
if (!visited[color][nei]) {
visited[color][nei] = true;
q.push({nei, steps + 1, color});
}
}
}
}
}
return res;
}
import java.util.*;
public class Solution {
public int[] shortestAlternatingPaths(int n, int[][] redEdges, int[][] blueEdges) {
Map<Integer, List<Integer>>[] graph = new HashMap[2];
for (int i = 0; i < 2; ++i) graph[i] = new HashMap<>();
for (int[] e : redEdges) graph[0].computeIfAbsent(e[0], k -> new ArrayList<>()).add(e[1]);
for (int[] e : blueEdges) graph[1].computeIfAbsent(e[0], k -> new ArrayList<>()).add(e[1]);
int[] res = new int[n];
Arrays.fill(res, -1);
boolean[][] visited = new boolean[2][n];
Queue<int[]> q = new LinkedList<>();
q.offer(new int[]{0, 0, -1}); // node, steps, prev_color
while (!q.isEmpty()) {
int[] curr = q.poll();
int node = curr[0], steps = curr[1], prevColor = curr[2];
if (res[node] == -1) res[node] = steps;
for (int color = 0; color < 2; ++color) {
if (color != prevColor) {
List<Integer> neighbors = graph[color].getOrDefault(node, new ArrayList<>());
for (int nei : neighbors) {
if (!visited[color][nei]) {
visited[color][nei] = true;
q.offer(new int[]{nei, steps + 1, color});
}
}
}
}
}
return res;
}
}
var shortestAlternatingPaths = function(n, redEdges, blueEdges) {
const graph = [new Map(), new Map()]; // 0: red, 1: blue
for (const [u, v] of redEdges) {
if (!graph[0].has(u)) graph[0].set(u, []);
graph[0].get(u).push(v);
}
for (const [u, v] of blueEdges) {
if (!graph[1].has(u)) graph[1].set(u, []);
graph[1].get(u).push(v);
}
const res = Array(n).fill(-1);
const visited = [Array(n).fill(false), Array(n).fill(false)];
const queue = [];
queue.push([0, 0, -1]); // node, steps, prev_color
while (queue.length) {
const [node, steps, prevColor] = queue.shift();
if (res[node] === -1) res[node] = steps;
for (let color = 0; color < 2; ++color) {
if (color !== prevColor) {
const neighbors = graph[color].get(node) || [];
for (const nei of neighbors) {
if (!visited[color][nei]) {
visited[color][nei] = true;
queue.push([nei, steps + 1, color]);
}
}
}
}
}
return res;
};
You are given a directed graph with n nodes, labeled from 0 to n - 1. Some of the edges are colored red, and some are colored blue. You are given two lists: redEdges and blueEdges, where each element is a pair [from, to] representing a directed edge from from to to of the respective color.
Your goal is to find the shortest path from node 0 to every other node such that the edges taken alternate in color (no two consecutive edges can be the same color). If a node is unreachable under these constraints, return -1 for that node.
n where result[i] is the length of the shortest alternating path from 0 to i, or -1 if not possible.This problem is a twist on the classic shortest path problem in graphs, but with the added constraint that the path must alternate between red and blue edges. A brute force approach would consider all possible paths, but that quickly becomes infeasible as the number of paths grows exponentially with the number of nodes and edges.
The key insight is to use Breadth-First Search (BFS), which naturally finds the shortest path in unweighted graphs. However, we need to track the color of the last edge used to ensure the "alternating" requirement is satisfied. This means that visiting the same node via a red edge and a blue edge are considered different "states".
To avoid revisiting the same state, we must track visits not just by node, but also by the color of the edge used to reach it.
We use a BFS approach, but with some modifications to handle alternating colors:
-1 for the starting node)visited[color][node]. This ensures we don't revisit the same node via the same color, which would create cycles or redundant searches.
-1.
This approach ensures that the shortest alternating path to each node is found efficiently, without redundant exploration.
Sample Input:
n = 3
redEdges = [[0,1],[1,2]]
blueEdges = []
Step-by-step:
0, with no previous color.0, can only take a red edge (since blue edges are empty). Move to node 1 via red, steps = 1.1, we must now take a blue edge (to alternate), but there are none. So, we cannot proceed to node 2 under the alternating rule.[0, 1, -1] — node 2 is unreachable with alternating colors.If there were both red and blue edges, the BFS would explore both, always alternating, and update the shortest path for each node as soon as it is reached.
O(n + e), where n is the number of nodes and e is the total number of edges. Each node is visited at most twice (once per color), and all edges are explored once per color.
O(n + e) for the adjacency lists, visited arrays, and BFS queue.
The problem is a variation of the shortest path search, with the twist that edge colors must alternate. By using BFS and keeping track of both the node and the color of the last edge used, we efficiently find the shortest alternating paths. The solution elegantly combines graph traversal with careful state management, ensuring we respect the color alternation constraint and avoid redundant exploration.