1129.Shortest Path with Alternating Colors
===

###### tags: `Medium`,`BFS`,`Graph`

[1129. Shortest Path with Alternating Colors](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]

**Constraints**:

* 1 <= `n` <= 100
* 0 <= `redEdges.length`, `blueEdges.length` <= 400
* `redEdges[i].length` == `blueEdges[j].length` == 2
* 0 <= `ai`, `bi`, `uj`, `vj` < `n`

### 解答

#### C++
##### 思路:
1. 從原點0開始走, path中的edge必須紅藍交叉, 找每個node與0的最小距離
2. 用BFS從原點開始走, 初始有選紅or藍edge兩種開始的選項, 故遍歷兩次每個node距離取最小
3. 每個node避免重複走, 紀錄該node是從紅edge或是從藍edge走到

class Solution {
public:
    void BFS(bool is_red_edge, vector<int>& res, vector<vector<int>>& red_node_adj, vector<vector<int>>& blue_node_adj)
    {
        vector<bool> red_visited(res.size(), false);
        vector<bool> blue_visited(res.size(), false);
        queue<int> q;
        q.push(0);
        if(is_red_edge)
            red_visited[0] = true;
        else
            blue_visited[0] = true;
        int step = 0;

        while(q.size())
        {
            int size = q.size();            
            while(size--)
            {
                int node = q.front(); q.pop();                
                res[node] = res[node]==-1 ? step : min(res[node], step);
                if(is_red_edge)
                {    
                    for(auto& n : red_node_adj[node])
                    {
                        if(red_visited[n])
                            continue;
                        red_visited[n] = true;
                        q.push(n);
                    }
                }
                else
                {
                    for(auto& n : blue_node_adj[node])
                    {
                        if(blue_visited[n])
                            continue;
                        blue_visited[n] = true;
                        q.push(n);
                    }
                }
            }
            is_red_edge = !is_red_edge;
            step++;
        }
    }
    vector<int> shortestAlternatingPaths(int n, vector<vector<int>>& redEdges, vector<vector<int>>& blueEdges) {
        vector<vector<int>> red_node_adj(n);
        vector<vector<int>> blue_node_adj(n);
        for(auto& v : redEdges)
            red_node_adj[v[0]].push_back(v[1]);
        for(auto& v : blueEdges)
            blue_node_adj[v[0]].push_back(v[1]);
        
        vector<int> res(n, -1);
        BFS(true, res, red_node_adj, blue_node_adj);
        BFS(false, res, red_node_adj, blue_node_adj);
        return res;
    }
};

Time: $O(2*n+2*e)$ `e`為紅藍edge總數, 每個點最多被拜訪兩次, 每個點最多走紅藍兩次edge
Extra Space: $O(n+e)$ Adjacency list儲存`e`個edge, BFS queue最多儲存`n`個node

> [name=XD] [time= Feb 11, 2023]

##### 思路
1. 紀錄下一個點與其邊的顏色`graph[u] = {v, color}`
2. 用BFS找最短路徑
3. 顏色不同的才可以繼續走
4. 走過的邊把他的`v`改成-1，使其不會被重複使用

enum class Color {kInit, kRed, kBlue};

class Solution {
public:
    vector<int> shortestAlternatingPaths(int n, vector<vector<int>>& redEdges, vector<vector<int>>& blueEdges) {
        vector<int> ans(n, -1);
        vector<vector<pair<int, Color>>> graph(n);
        queue<pair<int, Color>> q;
        for (auto edge : redEdges) {
            int a = edge[0], b = edge[1];
            graph[a].push_back({b, Color::kRed});
        }
        for (auto edge : blueEdges) {
            int u = edge[0], v = edge[1];
            graph[u].push_back({v, Color::kBlue});
        }
        q.push({0, Color::kInit});
        for (int step = 0; !q.empty(); step++) {
            for (int i = q.size(); i > 0; i--) {
                auto [u, prevColor] = q.front();
                q.pop();
                if (ans[u] == -1) ans[u] = step;
                for (auto& [v, color] : graph[u]) {
                    if (v == -1 || color == prevColor) continue;
                    q.push({v, color});
                    v = -1;
                }
            }
        }
        return ans;
    }
};

> [name=Yen-Chi Chen][time=Sat, Feb 11, 2023]

#### Javascript

function shortestAlternatingPaths(n, redEdges, blueEdges) {
  const graph = new Array(n).fill(0).map(() => []);
  for (const [v1, v2] of redEdges) {
    graph[v1].push([v2, 'red']);
  }
  for (const [v1, v2] of blueEdges) {
    graph[v1].push([v2, 'blue']);
  }

  const distances = new Array(n).fill(Infinity);
  // vertex可以重複走，但是edge不能重複
  const redVisited = new Array(n).fill(false);
  const blueVisited = new Array(n).fill(false);
  const queue = [[0, null, 0]];

  // 做BFS 走不同顏色的路
  while (queue.length) {
    const [node, color, step] = queue.shift();
    if (redVisited[node] && blueVisited[node]) continue;
    if (color === 'red') {
      if (redVisited[node]) continue;
      redVisited[node] = true;
    } else {
      if (blueVisited[node]) continue;
      blueVisited[node] = true;
    }

    // 更新距離
    distances[node] = Math.min(distances[node], step);

    for (const [vertex, nextColor] of graph[node]) {
      if (color === nextColor) continue; // 相同顏色的路無法走
      queue.push([vertex, nextColor, step + 1]);
    }
  }

  // 把無法到達的點設為 -1
  for (let i = 0; i < distances.length; i++) {
    if (distances[i] === Infinity) distances[i] = -1;
  }

  return distances;
}

> [name=Marsgoat][time=Feb 20, 2023]

### Reference

[回到題目列表](https://hackmd.io/@Marsgoat/leetcode_every_day)