Welcome to Subscribe On Youtube

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.

  • 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;
        }
    };
    
  • 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
    
    
  • 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];
    
    

All Problems

All Solutions