1129. Shortest Path with Alternating Colors

Description

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.

 

Example 1:

Input: n = 3, redEdges = [[0,1],[1,2]], blueEdges = []
Output: [0,1,-1]

Example 2:

Input: n = 3, redEdges = [[0,1]], blueEdges = [[2,1]]
Output: [0,1,-1]

 

Constraints:

• 1 <= n <= 100
• 0 <= redEdges.length, blueEdges.length <= 400
• redEdges[i].length == blueEdges[j].length == 2
• 0 <= ai, bi, uj, vj < n

Solutions

Solution 1: BFS

The problem is essentially a shortest path problem, which we can consider solving using BFS.

First, we preprocess all the edges, categorizing all the edges by color and storing them in a multi-dimensional array \(g\). Where \(g[0]\) stores all red edges, and \(g[1]\) stores all blue edges.

Next, we define the following data structures or variables:

• Queue \(q\): used to store the currently searched node and the color of the current edge;
• Set \(vis\): used to store the nodes that have been searched and the color of the current edge;
• Variable \(d\): used to represent the current search level, i.e., the distance from the currently searched node to the starting point;
• Array \(ans\): used to store the shortest distance from each node to the starting point. Initially, we initialize all elements in the \(ans\) array to \(-1\), indicating that the distance from all nodes to the starting point is unknown.

We first enqueue the starting point \(0\) and the color of the starting edge \(0\) or \(1\), indicating that we start from the starting point and the current edge is red or blue.

Next, we start the BFS search. Each time we take out a node \((i, c)\) from the queue, if the answer of the current node has not been updated, then we update the answer of the current node to the current level \(d\), i.e., \(ans[i] = d\). Then, we flip the color of the current edge \(c\), i.e., if the current edge is red, we change it to blue, and vice versa. We take out all edges corresponding to the color, if the other end node \(j\) of the edge has not been searched, then we enqueue it.

After the search is over, return the answer array.

The time complexity is \(O(n + m)\), and the space complexity is \(O(n + m)\). Here, \(n\) and \(m\) are the number of nodes and edges, respectively.

Python3JavaC++GoTypeScript

class Solution:
    def shortestAlternatingPaths(
        self, n: int, redEdges: List[List[int]], blueEdges: List[List[int]]
    ) -> List[int]:
        g = [defaultdict(list), defaultdict(list)]
        for i, j in redEdges:
            g[0][i].append(j)
        for i, j in blueEdges:
            g[1][i].append(j)
        ans = [-1] * n
        vis = set()
        q = deque([(0, 0), (0, 1)])
        d = 0
        while q:
            for _ in range(len(q)):
                i, c = q.popleft()
                if ans[i] == -1:
                    ans[i] = d
                vis.add((i, c))
                c ^= 1
                for j in g[c][i]:
                    if (j, c) not in vis:
                        q.append((j, c))
            d += 1
        return ans

class Solution {
    public int[] shortestAlternatingPaths(int n, int[][] redEdges, int[][] blueEdges) {
        List<Integer>[][] g = new List[2][n];
        for (var f : g) {
            Arrays.setAll(f, k -> new ArrayList<>());
        }
        for (var e : redEdges) {
            g[0][e[0]].add(e[1]);
        }
        for (var e : blueEdges) {
            g[1][e[0]].add(e[1]);
        }
        Deque<int[]> q = new ArrayDeque<>();
        q.offer(new int[] {0, 0});
        q.offer(new int[] {0, 1});
        boolean[][] vis = new boolean[n][2];
        int[] ans = new int[n];
        Arrays.fill(ans, -1);
        int d = 0;
        while (!q.isEmpty()) {
            for (int k = q.size(); k > 0; --k) {
                var p = q.poll();
                int i = p[0], c = p[1];
                if (ans[i] == -1) {
                    ans[i] = d;
                }
                vis[i][c] = true;
                c ^= 1;
                for (int j : g[c][i]) {
                    if (!vis[j][c]) {
                        q.offer(new int[] {j, c});
                    }
                }
            }
            ++d;
        }
        return ans;
    }
}

class Solution {
public:
    vector<int> shortestAlternatingPaths(int n, vector<vector<int>>& redEdges, vector<vector<int>>& blueEdges) {
        vector<vector<vector<int>>> g(2, vector<vector<int>>(n));
        for (auto& e : redEdges) {
            g[0][e[0]].push_back(e[1]);
        }
        for (auto& e : blueEdges) {
            g[1][e[0]].push_back(e[1]);
        }
        queue<pair<int, int>> q;
        q.emplace(0, 0);
        q.emplace(0, 1);
        bool vis[n][2];
        memset(vis, false, sizeof vis);
        vector<int> ans(n, -1);
        int d = 0;
        while (!q.empty()) {
            for (int k = q.size(); k; --k) {
                auto [i, c] = q.front();
                q.pop();
                if (ans[i] == -1) {
                    ans[i] = d;
                }
                vis[i][c] = true;
                c ^= 1;
                for (int& j : g[c][i]) {
                    if (!vis[j][c]) {
                        q.emplace(j, c);
                    }
                }
            }
            ++d;
        }
        return ans;
    }
};

func shortestAlternatingPaths(n int, redEdges [][]int, blueEdges [][]int) []int {
    g := [2][][]int{}
    for i := range g {
        g[i] = make([][]int, n)
    }
    for _, e := range redEdges {
        g[0][e[0]] = append(g[0][e[0]], e[1])
    }
    for _, e := range blueEdges {
        g[1][e[0]] = append(g[1][e[0]], e[1])
    }
    type pair struct{ i, c int }
    q := []pair{pair{0, 0}, pair{0, 1}}
    ans := make([]int, n)
    vis := make([][2]bool, n)
    for i := range ans {
        ans[i] = -1
    }
    d := 0
    for len(q) > 0 {
        for k := len(q); k > 0; k-- {
            p := q[0]
            q = q[1:]
            i, c := p.i, p.c
            if ans[i] == -1 {
                ans[i] = d
            }
            vis[i][c] = true
            c ^= 1
            for _, j := range g[c][i] {
                if !vis[j][c] {
                    q = append(q, pair{j, c})
                }
            }
        }
        d++
    }
    return ans
}

function shortestAlternatingPaths(
    n: number,
    redEdges: number[][],
    blueEdges: number[][],
): number[] {
    const g: [Graph, Graph] = [{}, {}];
    const ans = Array(n).fill(-1);
    const vis = Array.from({ length: n }, () => Array.from({ length: 2 }, () => false));
    let q: Vertex[] = [
        [0, 0],
        [0, 1],
    ];
    vis[0][0] = vis[0][1] = true;
    let d = 0;
    for (const [i, j] of redEdges) {
        (g[0][i] ??= []).push(j);
    }
    for (const [i, j] of blueEdges) {
        (g[1][i] ??= []).push(j);
    }
    while (q.length) {
        const qNext: Vertex[] = [];
        for (let [i, color] of q) {
            if (ans[i] === -1) {
                ans[i] = d;
            }
            color ^= 1;
            for (const j of g[color][i] ?? []) {
                if (!vis[j][color]) {
                    vis[j][color] = true;
                    qNext.push([j, color as Color]);
                }
            }
        }
        q = qNext;
        d++;
    }
    return ans;
}

type Graph = Record<number, number[]>;
type Color = 0 | 1;
type Vertex = [number, Color];

Comments