Problem Description

You have a directed graph with n nodes labeled from 0 to n - 1. The graph has two types of edges: red edges and blue edges. The graph may contain self-edges (edges from a node to itself) and parallel edges (multiple edges between the same pair of nodes).

You're given two arrays:

• redEdges[i] = [ai, bi] represents a directed red edge from node ai to node bi
• blueEdges[j] = [uj, vj] represents a directed blue edge from node uj to node vj

Your task is to find the shortest path from node 0 to every other node in the graph, with a special constraint: the colors of edges must alternate along the path. This means if you traverse a red edge, the next edge must be blue, and if you traverse a blue edge, the next edge must be red.

Return an array answer of length n where:

• answer[x] is the length of the shortest alternating-color path from node 0 to node x
• answer[x] is -1 if no such alternating path exists from node 0 to node x

For example, if you start at node 0 and take a red edge to node 1, then the next edge from node 1 (if you continue) must be a blue edge. The path length is counted as the number of edges traversed.

The key challenge is ensuring that edge colors alternate throughout the entire path while finding the minimum distance to each node.

Flowchart Walkthrough

First, let's pin down the algorithm using the Flowchart. Here's a step-by-step walkthrough:

Is it a graph?

• Yes: The problem explicitly mentions a directed graph with n nodes labeled from 0 to n-1, with red and blue edges connecting these nodes.

Is it a tree?

• No: The problem states there can be self-edges and parallel edges, which means it's not a tree structure. Trees don't have cycles or multiple edges between nodes.

Is the problem related to directed acyclic graphs?

• No: The graph can have cycles (including self-edges), so it's not necessarily acyclic.

Is the problem related to shortest paths?

• Yes: We need to find the shortest path from node 0 to every other node with the constraint that edge colors must alternate.

Is the graph Weighted?

• No: All edges have an implicit weight of 1 (we're counting the number of edges in the path, not summing weights). Each edge contributes exactly 1 to the path length.

BFS

• Yes: Since we have an unweighted graph and need to find shortest paths, BFS is the appropriate algorithm.

Conclusion: The flowchart suggests using BFS (Breadth-First Search) for finding the shortest alternating-color paths. BFS is ideal here because:

1. It explores nodes level by level, guaranteeing the shortest path in unweighted graphs
2. It can handle the additional constraint of alternating colors by tracking the color of the last edge used
3. It naturally finds the minimum distance from the source to all reachable nodes

Intuition

When we need to find shortest paths in an unweighted graph, BFS immediately comes to mind because it explores nodes level by level, guaranteeing we find the shortest distance first. However, this problem has a twist: we must alternate between red and blue edges.

The key insight is that we need to track not just which nodes we've visited, but also what color edge we used to reach them. Why? Because the color of the last edge determines what color we can use next. If we arrived at node 3 via a red edge, we can only leave via a blue edge.

This means the same node can be visited multiple times with different "states":

• Node 3 reached via a red edge (can only continue with blue)
• Node 3 reached via a blue edge (can only continue with red)

These are essentially different states in our search space. So instead of the traditional BFS where we track (node), we need to track (node, last_color).

Another crucial observation: we need to consider both starting possibilities. From node 0, we could take either a red edge or a blue edge as our first move. These lead to different alternating patterns:

• Starting with red: red → blue → red → blue...
• Starting with blue: blue → red → blue → red...

Both patterns might give us valid paths to different nodes, and we want the shortest among all valid paths.

The BFS approach naturally handles finding the minimum distance because when we first reach a node (regardless of the color state), we've found the shortest path to that node. We can track visited states as (node, color) pairs to avoid revisiting the same state, which would create unnecessary cycles in our search.

By organizing the edges by color in separate adjacency lists (g[0] for red, g[1] for blue), we can easily toggle between colors using XOR operation (c ^= 1), making the implementation clean and efficient.

Learn more about Breadth-First Search and Graph patterns.

Solution Approach

The solution implements BFS with state tracking to handle the alternating color constraint. Let's walk through the implementation step by step:

1. Graph Preprocessing

First, we organize the edges by color into separate adjacency lists:

g = [defaultdict(list), defaultdict(list)]
for i, j in redEdges:
    g[0][i].append(j)  # g[0] stores red edges
for i, j in blueEdges:
    g[1][i].append(j)  # g[1] stores blue edges

This structure allows us to easily access edges of a specific color: g[0] for red edges and g[1] for blue edges.

2. Initialization

We set up the necessary data structures:

• ans = [-1] * n: Initialize all distances to -1 (unreachable by default)
• vis = set(): Track visited states as (node, color) pairs to avoid revisiting
• q = deque([(0, 0), (0, 1)]): Start BFS with both color possibilities from node 0
  • (0, 0) means starting at node 0 with the ability to take red edges
  • (0, 1) means starting at node 0 with the ability to take blue edges
• d = 0: Current distance level in BFS

3. BFS Traversal

The BFS proceeds level by level:

while q:
    for _ in range(len(q)):  # Process all nodes at current distance
        i, c = q.popleft()
        if ans[i] == -1:
            ans[i] = d  # First time reaching node i, record distance
        vis.add((i, c))  # Mark this state as visited
        c ^= 1  # Flip color: 0→1 or 1→0
        for j in g[c][i]:  # Explore edges of the required color
            if (j, c) not in vis:
                q.append((j, c))
    d += 1  # Move to next distance level

Key Implementation Details:

• Color Alternation: The c ^= 1 operation flips the color. If we arrived via color c, we must leave via color 1-c.

• State Tracking: We track (node, color) pairs in vis to prevent revisiting the same state. This is crucial because visiting node 3 via red edge is different from visiting it via blue edge.

• First Visit Optimization: When we first reach a node (checked by ans[i] == -1), we immediately record the distance. Since BFS explores level by level, this guarantees the shortest path.

• Dual Starting Points: By initializing the queue with both (0, 0) and (0, 1), we explore paths starting with either color, ensuring we find the shortest valid path regardless of the starting edge color.

The algorithm terminates when the queue is empty, meaning all reachable states have been explored. The final ans array contains the shortest alternating-path distance to each node, or -1 if no such path exists.

Example Walkthrough

Let's walk through a small example to illustrate the solution approach.

Example Graph:

• n = 4
• redEdges = [[0,1], [1,2], [2,3]]
• blueEdges = [[0,2], [1,3]]

Visual Representation:

    Red edges:  0 → 1 → 2 → 3
    Blue edges: 0 → 2, 1 → 3

Step-by-Step BFS Execution:

Initialization:

• ans = [-1, -1, -1, -1]
• vis = {}
• q = [(0,0), (0,1)] // Start with both color options from node 0
• d = 0

Distance 0 (Processing node 0):

• Process (0,0):

  • ans[0] = 0 (first visit to node 0)
  • Add (0,0) to vis
  • Next color: 0^1 = 1 (blue)
  • Check blue edges from 0: finds edge 0→2
  • Add (2,1) to queue

• Process (0,1):

  • ans[0] already set, skip
  • Add (0,1) to vis
  • Next color: 1^1 = 0 (red)
  • Check red edges from 0: finds edge 0→1
  • Add (1,0) to queue

• Queue after d=0: [(2,1), (1,0)]

• ans = [0, -1, -1, -1]

Distance 1 (Processing nodes at distance 1):

• d = 1

• Process (2,1):

  • ans[2] = 1 (first visit to node 2)
  • Add (2,1) to vis
  • Next color: 1^1 = 0 (red)
  • Check red edges from 2: finds edge 2→3
  • Add (3,0) to queue

• Process (1,0):

  • ans[1] = 1 (first visit to node 1)
  • Add (1,0) to vis
  • Next color: 0^1 = 1 (blue)
  • Check blue edges from 1: finds edge 1→3
  • Add (3,1) to queue

• Queue after d=1: [(3,0), (3,1)]

• ans = [0, 1, 1, -1]

Distance 2 (Processing nodes at distance 2):

• d = 2

• Process (3,0):

  • ans[3] = 2 (first visit to node 3)
  • Add (3,0) to vis
  • Next color: 0^1 = 1 (blue)
  • No blue edges from 3

• Process (3,1):

  • ans[3] already set, skip
  • Add (3,1) to vis
  • Next color: 1^1 = 0 (red)
  • No red edges from 3

• Queue empty, algorithm terminates

• Final ans = [0, 1, 1, 2]

Path Analysis:

• Node 0: Distance 0 (starting point)
• Node 1: Distance 1 via path 0→1 (red edge)
• Node 2: Distance 1 via path 0→2 (blue edge)
• Node 3: Distance 2 via path 0→1→3 (red→blue) or 0→2→3 (blue→red)

The algorithm successfully finds the shortest alternating-color paths to all nodes!

Solution Implementation

Time and Space Complexity

Time Complexity: O(n + m)

The algorithm uses BFS to traverse the graph. In the worst case:

• Each node can be visited at most twice (once with red color and once with blue color), contributing O(n) to the complexity
• Each edge is processed at most once when exploring neighbors, contributing O(m) to the complexity where m is the total number of edges (len(redEdges) + len(blueEdges))
• The initialization of the graph takes O(m) time to process all edges
• The initialization of the answer array takes O(n) time

Therefore, the overall time complexity is O(n + m).

Space Complexity: O(n + m)

The space usage consists of:

• The graph structure g which stores all edges, requiring O(m) space
• The visited set vis which can contain at most 2n entries (each node with 2 possible colors), requiring O(n) space
• The queue q which in the worst case can contain O(n) nodes
• The answer array ans which stores n elements, requiring O(n) space

Therefore, the overall space complexity is O(n + m), where n is the number of nodes and m is the total number of edges.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Not Tracking States Properly - Using Only Node ID for Visited Set

One of the most common mistakes is tracking only the node ID in the visited set instead of the (node, color) pair. This leads to incorrect results because the same node can be reached via different color edges, and these represent different states in our alternating path problem.

Incorrect Implementation:

visited = set()
queue = deque([(0, 0), (0, 1)])

while queue:
    for _ in range(len(queue)):
        current_node, last_color = queue.popleft()
      
        # WRONG: Only checking node, not the state
        if current_node in visited:
            continue
        visited.add(current_node)  # WRONG: Only adding node
      
        # ... rest of the logic

Why This Fails: Consider a graph where node 2 can be reached from node 0 via:

• Path 1: Red edge (0→1) then Blue edge (1→2) - length 2
• Path 2: Blue edge (0→3) then Red edge (3→2) - length 2

If we only track node 2 as visited after the first path, we won't explore the second path. This could prevent us from finding valid alternating paths to other nodes that might only be reachable through the second path.

Correct Implementation:

visited = set()
queue = deque([(0, 0), (0, 1)])

while queue:
    for _ in range(len(queue)):
        current_node, last_color = queue.popleft()
      
        # CORRECT: Check the complete state
        if (current_node, last_color) in visited:
            continue
        visited.add((current_node, last_color))  # CORRECT: Add complete state
      
        # ... rest of the logic

2. Incorrect Color Alternation Logic

Another pitfall is misunderstanding when and how to alternate colors. The color should be flipped BEFORE exploring neighbors, not after.

Incorrect Implementation:

for neighbor in graph[last_color][current_node]:  # WRONG: Using same color
    if (neighbor, last_color) not in visited:
        queue.append((neighbor, last_color ^ 1))  # Flipping here is too late

Correct Implementation:

next_color = last_color ^ 1  # Flip color first
for neighbor in graph[next_color][current_node]:  # Use flipped color
    if (neighbor, next_color) not in visited:
        queue.append((neighbor, next_color))

3. Not Handling Both Starting Colors

Forgetting to initialize the queue with both color options from node 0 can lead to missing valid paths.

Incorrect Implementation:

queue = deque([(0, 0)])  # WRONG: Only starting with red edges

Correct Implementation:

queue = deque([(0, 0), (0, 1)])  # Start with both color options

This ensures we explore paths that begin with either a red or blue edge from node 0, finding the shortest valid alternating path regardless of the starting edge color.