Given a directed graph with nodes labeled 0 through n-1, where edge are colored either red or blue and may include self-loops and parallel edges.

Each [i, j] pair in red_edges represents a red directed edge from node i to node j. Similarly, each [i, j] pair in blue_edges represents a blue directed edge from node i to node j.

Compute an array result of length n where result[x] represents the length of the shortest path from node 0 to node x that alternates between red and blue edges. If no such path exists, set result[x] = -1.

Example 1:

Input: n = 3, red_edges = [[0,1],[1,2]], blue_edges = []
Output: [0,1,-1]

Example 2:

Input: n = 3, red_edges = [[0,1]], blue_edges = [[2,1]]
Output: [0,1,-1]

Example 3:

Input: n = 3, red_edges = [[1,0]], blue_edges = [[2,1]]
Output: [0,-1,-1]

Example 4:

Input: n = 3, red_edges = [[0,1]], blue_edges = [[1,2]]
Output: [0,1,2]

Example 5:

Input: n = 3, red_edges = [[0,1],[0,2]], blue_edges = [[1,0]]
Output: [0,1,1]

Constraints:

• 1 ≤ n ≤ 100
• red_edges.length ≤ 400
• blue_edges.length ≤ 400
• red_edges[i].length == blue_edges[i].length == 2
• 0 ≤ red_edges[i][j], blue_edges[i][j] < n

BFS Solution

function findAlternatingColorPaths(n, redEdges, blueEdges) {
    const redAdj = new Map();
    const blueAdj = new Map();
    
    for (const [u, v] of redEdges) {
        if (!redAdj.has(u)) redAdj.set(u, []);
        redAdj.get(u).push(v);
    }
    
    for (const [u, v] of blueEdges) {
        if (!blueAdj.has(u)) blueAdj.set(u, []);
        blueAdj.get(u).push(v);
    }
    
    const distances = Array(n).fill(Number.MAX_SAFE_INTEGER);
    const visitedRed = new Set();
    const visitedBlue = new Set();
    
    const queue = [
        {node: 0, steps: 0, lastColor: 'blue'},
        {node: 0, steps: 0, lastColor: 'red'}
    ];
    
    visitedRed.add(0);
    visitedBlue.add(0);
    
    while (queue.length > 0) {
        const {node, steps, lastColor} = queue.shift();
        
        distances[node] = Math.min(distances[node], steps);
        
        if (lastColor === 'red') {
            const neighbors = blueAdj.get(node) || [];
            for (const neighbor of neighbors) {
                if (!visitedBlue.has(neighbor)) {
                    visitedBlue.add(neighbor);
                    queue.push({node: neighbor, steps: steps + 1, lastColor: 'blue'});
                }
            }
        } else {
            const neighbors = redAdj.get(node) || [];
            for (const neighbor of neighbors) {
                if (!visitedRed.has(neighbor)) {
                    visitedRed.add(neighbor);
                    queue.push({node: neighbor, steps: steps + 1, lastColor: 'red'});
                }
            }
        }
    }
    
    return distances.map(d => d === Number.MAX_SAFE_INTEGER ? -1 : d);
}

Dynamic Programming Solution

function computeAlternatingPaths(n, redEdges, blueEdges) {
    const adjacency = Array(n).fill().map(() => Array(n).fill(null));
    const pathLengths = Array(n).fill().map(() => ({
        red: Number.MAX_SAFE_INTEGER,
        blue: Number.MAX_SAFE_INTEGER
    }));
    
    pathLengths[0].red = 0;
    pathLengths[0].blue = 0;
    
    for (const [from, to] of redEdges) {
        if (!adjacency[from][to]) adjacency[from][to] = {};
        adjacency[from][to].red = true;
    }
    
    for (const [from, to] of blueEdges) {
        if (!adjacency[from][to]) adjacency[from][to] = {};
        adjacency[from][to].blue = true;
    }
    
    const processingQueue = [0];
    
    while (processingQueue.length > 0) {
        const currentSize = processingQueue.length;
        
        for (let i = 0; i < currentSize; i++) {
            const source = processingQueue.shift();
            
            for (let target = 0; target < n; target++) {
                if (!adjacency[source][target]) continue;
                
                const edgeColors = adjacency[source][target];
                let shouldEnqueue = false;
                
                if (edgeColors.red) {
                    if (pathLengths[source].blue + 1 < pathLengths[target].red) {
                        pathLengths[target].red = pathLengths[source].blue + 1;
                        shouldEnqueue = true;
                    }
                }
                
                if (edgeColors.blue) {
                    if (pathLengths[source].red + 1 < pathLengths[target].blue) {
                        pathLengths[target].blue = pathLengths[source].red + 1;
                        shouldEnqueue = true;
                    }
                }
                
                if (shouldEnqueue) {
                    processingQueue.push(target);
                }
            }
        }
    }
    
    const results = [];
    for (let i = 0; i < n; i++) {
        const minPath = Math.min(pathLengths[i].red, pathLengths[i].blue);
        results[i] = minPath === Number.MAX_SAFE_INTEGER ? -1 : minPath;
    }
    
    return results;
}