1129. Leetcode Solution in Java

#java #programmiung

=============================================================
Descriptoin:
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]

=============================================================
Solution:

import java.util.*;

public class Solution {


    public int[] shortestAlternatingPaths(int n, int[][] red_edges, int[][] blue_edges) {


        // 用邻接表建图
        Map<Integer, List<Integer>>[] maps = (Map<Integer, List<Integer>>[]) (new HashMap[2]);
        maps[0] = new HashMap<>();
        maps[1] = new HashMap<>();
        for (int[] red_edge : red_edges) {


            int from = red_edge[0], to = red_edge[1];
            maps[0].putIfAbsent(from, new ArrayList<>());
            maps[0].get(from).add(to);
        }
        for (int[] blue_edge : blue_edges) {


            int from = blue_edge[0], to = blue_edge[1];
            maps[1].putIfAbsent(from, new ArrayList<>());
            maps[1].get(from).add(to);
        }

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

        Queue<int[]> queue = new ArrayDeque<>();
        queue.offer(new int[]{

    0, -1});
        res[0] = 0;

        // visited[i][0]指的是从红色边到达顶点i的这个状态有没有经历过
        boolean[][] visited = new boolean[n][2];

        int step = 0;
        while (!queue.isEmpty()) {


            step++;
            int size = queue.size();
            for (int i = 0; i < size; i++) {


                int[] cur = queue.poll();
                int pos = cur[0], color = cur[1];
                // 枚举下面一条路径的颜色
                for (int j = 0; j < 2; j++) {


                    // 如果颜色与上一条边颜色相同，则略过
                    if (j == color) {


                        continue;
                    }

                    if (maps[j].containsKey(pos)) {


                        for (int next : maps[j].get(pos)) {


                            if (!visited[next][j]) {


                                queue.offer(new int[]{

    next, j});
                                visited[next][j] = true;
                                // 第一次访问到next的时候就是最短距离
                                if (res[next] == -1) {


                                    res[next] = step;
                                }
                            }
                        }
                    }
                }
            }
        }

        return res;
    }
}