1129.Shortest Path with Alternating Colors

tags: Medium,BFS,Graph

1129. 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\ast n+2\ast e)$ e為紅藍edge總數, 每個點最多被拜訪兩次, 每個點最多走紅藍兩次edge
Extra Space:

$O(n+e)$ Adjacency list儲存e個edge, BFS queue最多儲存n個node

XD 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;
    }
};

Yen-Chi ChenSat, 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;
}

MarsgoatFeb 20, 2023

Reference

回到題目列表