Start learning free

LESSON 563 OF 667 · GRAPHS

Shortest Path with Alternating Colors in C++: BFS on (Vertex, Color)

Practice BFS, O(V+E) Read the full explanation

You get a directed graph with n nodes, numbered 0 to n - 1. Every edge is either red or blue. Each pair [u, v] in redEdges is a red edge from u to v. The pairs in blueEdges are the blue edges.

Return a vector answer with one number per node. For each node x, answer[x] is the fewest edges on an alternating path from node 0 to x.

A path is alternating when no two edges in a row have the same color. If no alternating path reaches x, answer[x] is -1. For node 0, the answer is always 0.

An edge can lead from a node back to itself. Two nodes can be joined by more than one edge.

Example 1

Input: n = 5, redEdges = [[0,1],[1,3],[2,4]], blueEdges = [[1,2],[3,4],[0,3]]
Output: [0,1,2,1,3]
Explanation: Node 3 is one blue edge away: 0 → 3.
But 3 → 4 is blue too, so 0 → 3 → 4 doesn't alternate.
The shortest alternating path to node 4 is 0 → 1 → 2 → 4.
Its colors are red, blue, red: 3 edges.

Example 2

Input: n = 4, redEdges = [[0,2],[2,3]], blueEdges = [[3,1]]
Output: [0,-1,1,-1]
Explanation: Node 2 is one red edge away: 0 → 2.
The next edge must be blue, but node 2 has no blue edge out.
So nodes 1 and 3 are never reached. Both get -1.

Example 3

Input: n = 3, redEdges = [[0,2],[2,1]], blueEdges = [[2,2]]
Output: [0,3,1]
Explanation: The blue loop at node 2 lets the color switch.
So node 1 is 3 edges away:
0 → 2 (red),
2 → 2 (blue),
2 → 1 (red).

Constraints

  • 1 to 100 nodes.
  • Up to 400 red edges and up to 400 blue edges.
  • Both ends of every edge are nodes from 0 to n - 1.
STEP 1 OF 14
    Ctrl + Enter to check

    C++ · GRAPHS

    Shortest Path With Alternating Colors in C++, explained

    Problem overview

    The method shortestAlternatingPaths receives n, the number of vertices of a directed graph, and two lists of directed edges: redEdges and blueEdges. Each entry [a, b] is an edge from a to b. The graph may contain self-edges and parallel edges. For every vertex x, the method must return the length of the shortest path from vertex 0 to x in which the edge colours alternate, or -1 if no such path exists. Vertex 0 itself has the answer 0.

    In the first example, n = 3, redEdges = [[0,1],[1,2]] and there are no blue edges. The path 0 to 1 uses one red edge, so vertex 1 is at distance 1. Going on to vertex 2 would take a second red edge in a row, which isn't allowed, so the answer is [0, 1, -1]. In the second example, red 0 → 1 followed by blue 1 → 2 alternates, giving [0, 1, 2].

    Approach: BFS where the state includes the last colour

    Counting edges in a graph with no restrictions is a job for breadth-first search (BFS). The colour rule adds a twist: whether you may use an edge depends on the colour of the edge you arrived by. Arriving at vertex 5 by a red edge means the next edge must be blue. Arriving by a blue edge means it must be red. Those are two different situations, even though the vertex is the same.

    So the thing to search over is not a vertex but a state: a pair (vertex, colour of the last edge). Every vertex gives two states. BFS over states finds the minimum number of edges to reach each state, and the answer for a vertex is the smaller of its two state distances. Because BFS reaches states in order of distance, the first time a vertex appears in any state is already its shortest alternating distance.

    A visited flag per vertex would not be enough. If vertex 2 was first reached by a red edge, a later arrival by a blue edge still has to be explored, because it can continue along red edges, which the first arrival could not. Tracking visited per (vertex, colour) keeps both.

    The start needs care too. The path from vertex 0 has no previous edge, so its first edge may be either colour. The search therefore begins with two states, (0, red) and (0, blue), both at distance 0.

    Step by step

    1. Build the adjacency lists. adj is a vector<array<vector<int>, 2>> of size n. For vertex u, adj[u][0] lists its red neighbours and adj[u][1] its blue ones.
    2. Fill the red lists. Loop over redEdges with auto& e and push e[1] onto adj[e[0]][0]. The graph is directed, so there is no reverse edge.
    3. Fill the blue lists the same way, into adj[e[0]][1].
    4. Prepare the answer. dist has n entries of -1, with dist[0] = 0. Unreachable vertices keep -1, exactly the required answer.
    5. Prepare the visited flags: a vector<array<bool, 2>> with one flag per vertex and arrival colour. Mark both states of vertex 0 as visited.
    6. Create the queue of tuple<int,int,int> and push {0, 0, 0} and {0, 1, 0}: vertex, colour of the last edge, distance.
    7. Loop while the queue is not empty. Each state enters at most once, so the loop ends.
    8. Take the front state and unpack it with auto [u, color, d], then pop it.
    9. Flip the colour: nextColor = 1 - color. Then loop over adj[u][nextColor], the neighbours reachable by an edge of the required colour.
    10. Skip visited states. If visited[v][nextColor] is false, continue.
    11. Mark it as visited right away, when the state is queued, so it can't be queued twice.
    12. Record the distance d + 1 in dist[v] if dist[v] is still -1. BFS processes states by increasing distance, so the first value written is the smallest and is never replaced.
    13. Queue the new state {v, nextColor, d + 1}.
    14. Return dist once the queue is empty.

    The solution in C++

    class Solution {
    public:
        vector<int> shortestAlternatingPaths(int n, vector<vector<int>>& redEdges, vector<vector<int>>& blueEdges) {
            vector<array<vector<int>, 2>> adj(n);
            for (auto& e : redEdges) {
                adj[e[0]][0].push_back(e[1]);
            }
            for (auto& e : blueEdges) {
                adj[e[0]][1].push_back(e[1]);
            }
            vector<int> dist(n, -1);
            dist[0] = 0;
            vector<array<bool, 2>> visited(n, {false, false});
            visited[0][0] = visited[0][1] = true;
            queue<tuple<int,int,int>> q;
            q.push({0, 0, 0});
            q.push({0, 1, 0});
            while (!q.empty()) {
                auto [u, color, d] = q.front();
                q.pop();
                int nextColor = 1 - color;
                for (int v : adj[u][nextColor]) {
                    if (!visited[v][nextColor]) {
                        visited[v][nextColor] = true;
                        if (dist[v] == -1) {
                            dist[v] = d + 1;
                        }
                        q.push({v, nextColor, d + 1});
                    }
                }
            }
            return dist;
        }
    };
    

    The C++ details:

    • Arrays inside a vector. std::array<vector<int>, 2> is a fixed-size array of two vectors, so adj[u][0] and adj[u][1] are two separate lists. It needs <array>. Constructing adj(n) gives every vertex two empty lists.
    • Brace initialisation. vector<array<bool, 2>> visited(n, {false, false}) fills each entry with two false values. The chained assignment visited[0][0] = visited[0][1] = true works because an assignment returns the assigned value.
    • Tuples and structured bindings. auto [u, color, d] = q.front(); (C++17) copies the front tuple and names its three parts. Because it copies, calling q.pop() afterwards is safe. Writing auto& there would leave the names referring to a destroyed element.
    • Pushing a tuple with braces. q.push({v, nextColor, d + 1}) builds the tuple<int,int,int> in place. Plain int values match the element types, so nothing needs converting.
    • Colour as an index. Using 0 for red and 1 for blue lets 1 - color flip the colour and the number work directly as an array index.
    • The size of the lists. Each vertex has its lists in one place, so the neighbour loop for (int v : adj[u][nextColor]) only sees edges of the colour that is allowed next.

    Complexity

    Time: O(n + r + b), where r and b are the numbers of red and blue edges. There are 2n states, each enters the queue at most once, and each state scans the list of one colour for its vertex. Across the whole search every edge is scanned at most once, from the state where its colour is the next one needed.

    Space: O(n + r + b). The adjacency lists hold every edge, and dist, the visited flags and the queue take O(n).

    Edge cases and common mistakes

    • One visited flag per vertex. It breaks cases like redEdges = [[0,1]], blueEdges = [[2,1],[1,2]]. Vertex 1 is reached by red, and vertex 2 is reached from it by blue. A single flag could block a legitimate second arrival at some vertex.
    • Seeding only one colour. Starting with (0, red) alone would force every path to begin with a blue edge. Both starting states are needed.
    • Overwriting dist. A vertex can be reached again later in the other colour, along a longer path. The check for -1 keeps the first, shortest value.
    • Vertex 0 and cycles. The answer for vertex 0 is 0 even if a cycle leads back to it, because dist[0] is set before the search and never changed.
    • Self-edges and parallel edges. They are harmless. A self-edge leads to a state that is either already visited or gets visited once, and duplicate edges are skipped by the visited check.
    • Marking when popped. Setting the flag after taking a state from the queue lets the same state be queued many times. Mark when pushing.
    • Two edges of the same colour. In the first example, 0 → 1 → 2 is two red edges, so vertex 2 stays at -1.

    Testing

    • n = 3, redEdges = [[0,1],[1,2]], blueEdges = [] gives [0, 1, -1].
    • n = 3, redEdges = [[0,1]], blueEdges = [[2,1],[1,2]] gives [0, 1, 2].
    • n = 3, redEdges = [[0,1],[0,2]], blueEdges = [[1,0]] gives [0, 1, 1].
    Keep going with C++650+ step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free