颜色交替的最短路径

题目链接

颜色交替的最短路径

题目描述

注意

返回长度为n的数组answer，其中answer[x]是从节点0到节点x的红色边和蓝色边交替出现的最短路径的长度
图中每条边为红色或者蓝色，且可能存在自环或平行边

解答思路

可以使用广度优先遍历从0开始找到其相邻的点，需要注意的是，因为路径需要颜色交替，所以需要将每个点对应不同颜色边的邻接点保存到两个的map中，同时将上一条边的颜色传到下一次bfs中，根据bfs的层数填入到达任意一个节点颜色交替的最短路径
需要注意的是，图中可能存在自环或平行边，所以在bfs的过程中，不能重复经过同一个节点导致死循环，需要保存整个过程中经过的节点
保存节点时还需要注意的是以蓝色边经过某个节点和以红色边经过相同节点不应该视作重复经过（后续的边不同）

代码

class Solution {
    public int[] shortestAlternatingPaths(int n, int[][] redEdges, int[][] blueEdges) {
        int[] res = new int[n];
        Arrays.fill(res, -1);
        Map<Integer, Set<Integer>> redMap = fillMap(redEdges);
        Map<Integer, Set<Integer>> blueMap = fillMap(blueEdges);
        // 以红色边开始
        bfs(redMap, blueMap, res, true);
        // 以蓝色边开始
        bfs(redMap, blueMap, res, false);
        return res;
    }

    public Map<Integer, Set<Integer>> fillMap(int[][] edges) {
        Map<Integer, Set<Integer>> map = new HashMap<>();
        for (int i = 0; i < edges.length; i++) {
            int p1 = edges[i][0];
            int p2 = edges[i][1];
            if (map.get(p1) == null) {
                map.put(p1, new HashSet<>());
            }
            Set<Integer> set = map.get(p1);
            set.add(p2);
        }
        return map;
    }
    
    public void bfs(Map<Integer, Set<Integer>> redMap, Map<Integer, Set<Integer>> blueMap, int[] res, boolean isRed) {
        // 上一次到达的节点
        Deque<Integer> pointDq = new ArrayDeque<>();
        // 红色边到达过的节点
        Set<Integer> passRedSet = new HashSet<>();
        // 蓝色边到达过的节点
        Set<Integer> passBlueSet = new HashSet<>();
        pointDq.offer(0);
        int depth = 0;
        while (!pointDq.isEmpty()) {
            int size = pointDq.size();
            for (int i = 0; i < size; i++) {
                int p1 = pointDq.poll();
                res[p1] = (res[p1] == -1 ? depth : Math.min(res[p1], depth));
                Set<Integer> set = isRed ? redMap.get(p1) : blueMap.get(p1);
                if (set == null || set.size() == 0) {
                    continue;
                }
                for (int p2 : set) {
                    // 防止重复添加死循环
                    if ((isRed && passRedSet.add(p2)) || (!isRed && passBlueSet.add(p2))) {
                        pointDq.offer(p2);
                    }
                }
            }
            isRed = !isRed;
            depth++;
        }
    }
}