# Leetcode template
###### tags: `leetcode` `daily` `BFS`

[題目連結](https://leetcode.com/problems/shortest-path-with-alternating-colors/description/)

# Method
:::info
:bulb: **作法講解**:
晚點補寫

:::
n = node size
m = edge size
TC: O(N+M) SC: O(N+M)
:::spoiler 完整程式碼

class Solution {
public:
    void find_next_node(int node, int lcolor, queue<pair<int, int>> &q, 
                        vector<vector<int>> &adj, vector<int> &output, int step,
                        vector<vector<bool>> &visited) 
    {
        int cur_color = 1 - lcolor;

        for(int next : adj[node]) {
            if(visited[next][cur_color]) {
                continue;
            }
            q.push({next, cur_color});
            visited[next][cur_color] = true;

            if(output[next] >= 0) {
                continue;
            }
            output[next] = step;
        }
    }
    vector<int> shortestAlternatingPaths(int n, vector<vector<int>>& redEdges, vector<vector<int>>& blueEdges) {
        vector<int> output(n, -1);
        vector<vector<bool>> visited(n, vector<bool>(2, false));
        vector<vector<int>> radj(n);
        vector<vector<int>> badj(n);
        int step = 0;
        //first: node, second: last color
        //if node == 0, last color = -1
        queue<pair<int, int>> q;

        for(vector<int> &e : redEdges) {
            radj[e[0]].push_back(e[1]);
        }
        for(vector<int> &e : blueEdges) {
            badj[e[0]].push_back(e[1]);
        }

        output[0] = 0;
        visited[0][0] = true;
        visited[0][1] = true;
        q.push({0, -1});

        while(!q.empty()) {
            int size = q.size();
            step++;
            for(int i = 0 ; i < size ; i++) {
                int node = q.front().first;
                int lcolor = q.front().second;
                q.pop();

                if(lcolor != 0) {
                    find_next_node(node, 1, q, radj, output, step, visited);
                }
                if(lcolor != 1) {
                    find_next_node(node, 0, q, badj, output, step, visited);
                }
            }
        }
        
        return output;
    }
};

:::