Solution Explanation: Shortest Path with Alternating Colors

This problem asks for the shortest path between node 0 and all other nodes in a directed graph, with the constraint that the colors of the edges must alternate (red, blue, red, ... or blue, red, blue, ...). We can efficiently solve this using Breadth-First Search (BFS).

Approach:

1. Graph Representation: We represent the graph using two adjacency lists: one for red edges and one for blue edges. This allows us to easily access the neighbors of a node for each color.

2. BFS with Color Tracking: The BFS algorithm is modified to track the current edge color. Each node in the queue is represented as a tuple (node, color), where node is the node's index and color indicates the color of the last edge traversed (0 for red, 1 for blue).

3. Alternating Colors: When processing a node, we explore its neighbors using the opposite color. If the current color is red (0), we explore blue edges; if blue (1), we explore red edges. This ensures the alternating color constraint is met.

4. Shortest Path Distance: The distance from node 0 to each node is determined by the level in the BFS traversal. We use an array ans to store the shortest distance for each node, initializing it with -1 to indicate that the node is unreachable.

5. Visited Tracking: A vis set (or 2D boolean array) is crucial to avoid cycles and ensure we only visit each node with a specific color once. The key is (node, color), preventing revisits with the same color.

Time Complexity: O(V + E), where V is the number of nodes (n) and E is the number of edges (total number of red and blue edges). The BFS algorithm visits each node and edge at most once.

Space Complexity: O(V + E), dominated by the adjacency lists and the queue in the worst case (when the graph is dense).

Code Implementation (Python):

from collections import defaultdict, deque
 
class Solution:
    def shortestAlternatingPaths(self, n: int, redEdges: List[List[int]], blueEdges: List[List[int]]) -> List[int]:
        g = [defaultdict(list), defaultdict(list)]  # Adjacency lists for red (0) and blue (1) edges
        for u, v in redEdges:
            g[0][u].append(v)
        for u, v in blueEdges:
            g[1][u].append(v)
 
        ans = [-1] * n             # Shortest distance to each node
        ans[0] = 0                 # Distance to starting node is 0
        vis = set()                # Visited nodes with colors
 
        q = deque([(0, 0), (0, 1)]) # Queue of (node, color) tuples
        vis.add((0,0))
        vis.add((0,1))
        d = 0                       # Level/Distance
 
        while q:
            for _ in range(len(q)): # Process nodes at current level
                i, c = q.popleft()
                
                # Explore neighbors with opposite color
                next_color = 1 - c
                for neighbor in g[next_color][i]:
                    if (neighbor, next_color) not in vis:
                        vis.add((neighbor, next_color))
                        q.append((neighbor, next_color))
                        ans[neighbor] = d + 1
 
 
            d += 1 #Increment distance for next level
 
        return ans
 

The code in other languages (Java, C++, Go, TypeScript) follows a similar structure, adapting the data structures and syntax accordingly. The core algorithm remains the same: BFS with color tracking and efficient visited node management.