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
- Build the adjacency lists.
adjis avector<array<vector<int>, 2>>of sizen. For vertexu,adj[u][0]lists its red neighbours andadj[u][1]its blue ones. - Fill the red lists. Loop over
redEdgeswithauto& eand pushe[1]ontoadj[e[0]][0]. The graph is directed, so there is no reverse edge. - Fill the blue lists the same way, into
adj[e[0]][1]. - Prepare the answer.
disthasnentries of-1, withdist[0] = 0. Unreachable vertices keep-1, exactly the required answer. - 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. - Create the queue of
tuple<int,int,int>and push{0, 0, 0}and{0, 1, 0}: vertex, colour of the last edge, distance. - Loop while the queue is not empty. Each state enters at most once, so the loop ends.
- Take the front state and unpack it with
auto [u, color, d], then pop it. - Flip the colour:
nextColor = 1 - color. Then loop overadj[u][nextColor], the neighbours reachable by an edge of the required colour. - Skip visited states. If
visited[v][nextColor]is false, continue. - Mark it as visited right away, when the state is queued, so it can't be queued twice.
- Record the distance
d + 1indist[v]ifdist[v]is still-1. BFS processes states by increasing distance, so the first value written is the smallest and is never replaced. - Queue the new state
{v, nextColor, d + 1}. - Return
distonce 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, soadj[u][0]andadj[u][1]are two separate lists. It needs<array>. Constructingadj(n)gives every vertex two empty lists. - Brace initialisation.
vector<array<bool, 2>> visited(n, {false, false})fills each entry with twofalsevalues. The chained assignmentvisited[0][0] = visited[0][1] = trueworks 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, callingq.pop()afterwards is safe. Writingauto&there would leave the names referring to a destroyed element. - Pushing a tuple with braces.
q.push({v, nextColor, d + 1})builds thetuple<int,int,int>in place. Plainintvalues match the element types, so nothing needs converting. - Colour as an index. Using 0 for red and 1 for blue lets
1 - colorflip 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-1keeps 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 → 2is 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].
