将红色和蓝色的边分别建图 搜索时使用数组记录 [当前节点,需要使用的颜色] 交替搜索即可 用0
表示红色,1
表示蓝色,对于颜色i
, 下一次的颜色即为i ^ 1
复杂度分析: 时间复杂度:O(n+r+b),其中
n
是节点数,r
是红边数,b
是蓝边数。 空间复杂度:O(n+r+b)
class Solution {
public int[] shortestAlternatingPaths(int n, int[][] redEdges, int[][] blueEdges) {
List<Integer>[][] es = new List[2][n];
for(int i = 0; i < n; i++){
es[0][i] = new ArrayList();
es[1][i] = new ArrayList();
}
for(int[] r : redEdges) es[0][r[0]].add(r[1]);
for(int[] b : blueEdges) es[1][b[0]].add(b[1]);
int[] ans = new int[n];
Arrays.fill(ans, -1);
ans[0] = 0;
Queue<int[]> q = new LinkedList();
q.offer(new int[]{0, 0});
q.offer(new int[]{0, 1});
boolean[][] visited = new boolean[2][n];
int dis = 1;
while(!q.isEmpty()){
for(int i = q.size(); i > 0; i--){
int[] pos = q.poll();
for(int next : es[pos[1]][pos[0]]){
if(visited[pos[1] ^ 1][next]) continue;
visited[pos[1] ^ 1][next] = true;
if(ans[next] == -1) ans[next] = dis;
q.offer(new int[]{next, pos[1] ^ 1});
}
}
dis++;
}
return ans;
}
}