Determine if there is a path with alternating edge colours in directed graph

Question

Given directed graph $G = \langle V, E \rangle$, such that some vertices are red, and some vertices are black, and some edges are blue or green, decide for all vertices $v \in V$ if there is path from $v$ to some red vertex with alternating edge colours (no edges of same colour are adjacent in the path, e.g. blue -> green -> blue -> ...).

If $G$ is acyclic, the problem looks simple - just use DFS. But how can one solve it if there are cycles in $G$?

Answer 1

Let's construct a new graph $G'$.

Every vertex $u$ from $G$ will become a pair of vertexes in $G'$, namely $u_{blue}$ and $u_{green}$ (index stands for the color of incoming edge).

Edge $u_{c_1}\rightarrow w_{c_2}$ in $G'$ exists iff

1. There is an edge $u \rightarrow w$ in $G$ colored $c_2$
2. $c_1 \ne c_2$

Now it's easy to see that every path in $G'$ corresponds to a color-alternating path in $G$ (and the converse is also true), i.e. color-alternating path from $v$ to $u$ in $G$ exists iff there is path from $v_{c_1}$ to $u_{c_2}$ in $G'$ for some $c_1, c_2$.