![image-20230202085239180](https://img.slcp.top/image-20230202085239180.png)
## 解题思路：广度优先搜索
将红色和蓝色的边分别建图
搜索时使用数组记录 [当前节点，需要使用的颜色] 交替搜索即可
用` 0 `表示红色，` 1 `表示蓝色，对于颜色` i `， 下一次的颜色即为` i ^ 1 `

> 复杂度分析：
时间复杂度：O(n+r+b)，其中` n `是节点数，` r `是红边数，` b `是蓝边数。
空间复杂度：`O(n+r+b)`

## 代码
```java
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;
    }
}
```

1129. 颜色交替的最短路径

目录