Find the shortest distance from node 0 to every node in a directed graph when consecutive edges must alternate colors.
You are given a directed graph with nodes labeled from $0n-1$. The graph contains two kinds of directed edges: red and blue.
A valid path is one where the colors of consecutive edges strictly alternate. In other words, if one edge is red, the next edge must be blue, and vice versa.
Return an array dist of length where dist[i] is the length of the shortest valid path from node 0 to node i. If node i cannot be reached under the alternating-color rule, set dist[i] = -1.
The path length is the number of edges used.
Input Format
- An integer
n. - Two edge lists describing directed red and blue edges.
- Each edge is of the form
[from, to].
You may assume nodes are labeled 0 to n-1.
Output Format
- Return an integer array of length
n. dist[i]is the minimum number of edges in any valid alternating-color path from0toi, or-1if no such path exists.
Constraints
- Edges are directed.
- Multiple edges and repeated endpoints may appear.
- Paths must alternate colors on every step.
- The start node is
0.
Example 1
Input
n = 3 redEdges = [[0,1],[1,2]] blueEdges = []
Output
[0,1,-1]
Explanation
Node 1 is reachable in one red edge. Node 2 would require two red edges in a row, which is invalid, so it is unreachable.
Example 2
Input
n = 3 redEdges = [[0,1]] blueEdges = [[1,2]]
Output
[0,1,2]
Explanation
Use a red edge from 0 to 1, then a blue edge from 1 to 2. The alternating rule is satisfied throughout.
Premium problem context
Unlock deeper context for this problem
Premium adds guided hints, editorial links, similar variants, discussion resources, and concept maps so you can understand why a problem matters, not just solve it once.