Shortest path with alternating colors

Breadth-First Search Graph Theory

47.7% acceptance

Feb 25, 2026

3702

206

You are given an integer n, the number of nodes in a directed graph where the nodes are labeled from 0 to n - 1. Each edge is red or blue in this graph, and there could be self-edges and parallel edges. You are given two arrays redEdges and blueEdges where: redEdges[i] = [ai, bi] indicates that there is a directed red edge from node ai to node bi in the graph, and blueEdges[j] = [uj, vj] indicates that there is a directed blue edge from node uj to node vj in the graph. Return an array answer of length n, where each answer[x] is the length of the shortest path from node 0 to node x such that the edge colors alternate along the path, or -1 if such a path does not exist.

Solution

Rust

Time O(n * m)

Space O(n * m)

LeetCode

solution.rs

use std::collections::VecDeque;

impl Solution {
  pub fn shortest_alternating_paths(n: i32, red_edges: Vec<Vec<i32>>, blue_edges: Vec<Vec<i32>>) -> Vec<i32> {
    let n = n as usize;
    // adj[node] = list of (neighbor, color): 0=red, 1=blue
    let mut adj: Vec<Vec<(usize, usize)>> = vec![vec![]; n];
    for e in &red_edges  { adj[e[0] as usize].push((e[1] as usize, 0)); }
    for e in &blue_edges { adj[e[0] as usize].push((e[1] as usize, 1)); }

    let mut dist = vec![-1i32; n];
    // visited[node][color]
    let mut visited = vec![[false; 2]; n];
    let mut queue = VecDeque::new();
    dist[0] = 0;
    // Start with both colors from node 0
    queue.push_back((0usize, 0usize, 0i32)); // (node, last_color, dist)
    queue.push_back((0usize, 1usize, 0i32));
    visited[0][0] = true;
    visited[0][1] = true;

    while let Some((node, last_color, d)) = queue.pop_front() {
      for &(next, color) in &adj[node] {
        if color != last_color && !visited[next][color] {
          visited[next][color] = true;
          if dist[next] == -1 { dist[next] = d + 1; }
          queue.push_back((next, color, d + 1));
        }
      }
    }
    dist
  }
}