LeetCode Q 1128 - Shortest Path with Alternating Colors

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

Solution: BFS, choose next node from map with different color.

Code:

private static final int RED = 1, BLUE = 2;

public int[] shortestAlternatingPaths(int n, int[\][] red_edges, int[\][] blue_edges) {
  
  Map<Integer, Set<Integer>> redMap = new HashMap<>();
  Map<Integer, Set<Integer>> blueMap = new HashMap<>();

  for (int i = 0; i < n; i++) {
    redMap.put(i, new HashSet<>());
    blueMap.put(i, new HashSet<>());
  }

  for (int re: red_edges) {
    redMap.get(re[0]).add(re[1]);
    redMap.get(re[1]).add(re[0]);
  }

  for (int be: blue_edges) {
    blueMap.get(be[0]).add(be[1]);
    blueMap.get(be[1]).add(be[0]);
  }

  int[] res = new int[n];
  Arrays.fill(res, -1);

  Queue<int[]> que = new LinkedList<>();

  // node, color (1: red, 2: blue)
  que.offer(new int[]{0, 0}); que.offer(new int[]{0, 0});
  int dist = 0;

  Set<String> seen = new HashSet<>();

  while (!que.isEmpty()) {
    int size = que.size();
    
    for (int i = 0; i < size; i++) {
      int[] curr = que.poll();
      int node = curr[0], color = curr[1];

      if (seen.contains(node+" "+color)) continue;
      seen.add(node + " " + color);

      if (res[node] == -1) res[node] = dist;

      if (color == RED || color == 0) {
        for (int next: blueMap.get(color)) {
          que.offer(new int[]{next, BLUE});
        }
      }

      if (color == BLUE || color == 0) {
        for (int next: redMap.get(color)) {
          que.offer(new int[]{next, RED});
        }
      }
    }

    dist++;
  }

  return res;
}

Reprint policy