source: https://leetcode.com/problems/shortest-path-with-alternating-colors/
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]
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 |
class Solution { public int[] shortestAlternatingPaths(int n, int[][] redEdges, int[][] blueEdges) { //Graph containing Red edges Map<Integer, List<Integer>> red = new HashMap<>(); for(int[] edge: redEdges){ addEdge(red, edge[0], edge[1]); } //Graph containing blue edges Map<Integer, List<Integer>> blue = new HashMap<>(); for(int[] edge: blueEdges){ addEdge(blue, edge[0], edge[1]); } int[] res = bfs(n, red, blue); return res; } private int[] bfs(int n, Map<Integer, List<Integer>> red, Map<Integer, List<Integer>> blue){ int[] res = new int[n]; Arrays.fill(res, -1); //visited edges Set<String> visited = new HashSet<>(); //initialize it visited.add(0+":"+0); visited.add(1+":"+0); Queue<Pair> next = new LinkedList<>(); next.add(new Pair(-1, 0)); int level = 0; while(!next.isEmpty()){ int size = next.size(); for(int i=0;i<size;i++){ Pair p = next.poll(); //assign level only if it hasn't been initialized yet if(res[p.val]==-1){ res[p.val] = level; } //color = blue(1) or -1 if(p.color!=0){ //the current edge is from blue, next edge should be from red if(red.containsKey(p.val)){ for(int adj: red.get(p.val)){ if(!visited.contains(0+":"+adj)){ visited.add(0+":"+adj); next.offer(new Pair(0, adj)); } } } } //color = red(0) or -1 if(p.color!=1){//the current edge is from red, next edge should be from blue if(blue.containsKey(p.val)){ for(int adj: blue.get(p.val)){ if(!visited.contains(1+":"+adj)){ visited.add(1+":"+adj); next.offer(new Pair(1, adj)); } } } } } level++; } return res; } private void addEdge(Map<Integer, List<Integer>> map, int a, int b){ List<Integer> l = map.getOrDefault(a, new ArrayList<>()); l.add(b); map.put(a, l); } static class Pair{ int color; int val; public Pair(int color, int val){ this.color = color; this.val = val; } } } |