Consider a directed graph, with nodes labelled 0, 1, ..., n-1.  In this graph, each edge is either red or blue, and there could be self-edges or parallel edges.

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

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 doesn't exist).

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

The shortest path of color alternation.

In a directed graph, nodes are marked as 0, 1, n-1. Each edge in the graph is either red or blue, and there are self rings or parallel edges.

red_ Each [i, j] pair in edges represents a red directed edge from node i to node j. Similarly, blue_ Each [i, j] pair in edges represents a blue directed edge from node i to node j.

Returns an array answer of length n, where answer[X] is the length of the shortest path from node 0 to node X with alternating red and blue edges. If no such path exists, answer[x] = -1.

Source: LeetCode
Link: https://leetcode-cn.com/problems/shortest-path-with-alternating-colors
The copyright belongs to LinkedIn. For commercial reprint, please contact the official authorization. For non-commercial reprint, please indicate the source.

This is a graph theory problem. The title says that it is a directed graph and finds the shortest path from 0 to all other nodes alternately in red and blue. Then the idea should be BFS. Since it is the problem of the graph, what we should do at the beginning is to create the graph. The special thing about this problem is that there may be both red and blue edges between two nodes, so we choose to create an adjacency matrix here. If -n is placed in the matrix, the two points are not connected; If 1 is placed in the matrix, it means that there is a red edge between the two points, -1 means that there is a blue edge. Both red and blue are represented by 0.

Since it is BFS, we put (0, 1) and (0, -1) in the queue at the beginning, indicating that the point to 0 has two conditions: red and blue. When popping from the queue, we judge whether there is an effective edge from 0 to all other points, and the color is opposite to the previous color. At the same time, in order to prevent dead loops, we need to use a hashset to record the color of the traversed points and edges (to record the color of the edges used to access a point).

Time O(V + E)

Space O(n) - hashset

Java implementation

 1 class Solution {
 2     public int[] shortestAlternatingPaths(int n, int[][] red_edges, int[][] blue_edges) {
 3         int[][] g = new int[n][n];
 4         buildGraph(g, n, red_edges, blue_edges);
 5 
 6         Queue<int[]> queue = new LinkedList<>();
 7         // [node, color]
 8         queue.offer(new int[] { 0, 1 });
 9         queue.offer(new int[] { 0, -1 });
10         int step = 0;
11         int[] res = new int[n];
12         Arrays.fill(res, Integer.MAX_VALUE);
13         res[0] = 0;
14 
15         // Record whether a point is in a certain color visited too
16         Set<String> visited = new HashSet<>();
17         while (!queue.isEmpty()) {
18             int size = queue.size();
19             step++;
20             for (int i = 0; i < size; i++) {
21                 int[] cur = queue.poll();
22                 int node = cur[0];
23                 int color = cur[1];
24                 int oppoColor = -color;
25 
26                 for (int j = 1; j < n; j++) {
27                     if (g[node][j] == oppoColor || g[node][j] == 0) {
28                         if (!visited.add(j + "" + oppoColor)) {
29                             continue;
30                         }
31                         queue.offer(new int[] { j, oppoColor });
32                         res[j] = Math.min(res[j], step);
33                     }
34                 }
35             }
36         }
37 
38         for (int i = 1; i < n; i++) {
39             if (res[i] == Integer.MAX_VALUE) {
40                 res[i] = -1;
41             }
42         }
43         return res;
44     }
45 
46     private void buildGraph(int[][] g, int n, int[][] red_edges, int[][] blue_edges) {
47         for (int i = 0; i < n; i++) {
48             // Initialize as-n
49             Arrays.fill(g[i], -n);
50         }
51 
52         // Red edge marked as 1
53         for (int[] e : red_edges) {
54             int from = e[0];
55             int to = e[1];
56             g[from][to] = 1;
57         }
58 
59         for (int[] e : blue_edges) {
60             int from = e[0];
61             int to = e[1];
62             // If there is a red edge, mark it as 0
63             // If there is no red edge, mark it as-1
64             if (g[from][to] == 1) {
65                 g[from][to] = 0;
66             } else {
67                 g[from][to] = -1;
68             }
69         }
70     }
71 }

LeetCode topic summary