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$?

  • $\begingroup$ Why do the presence of cycles bother you? I mean, DFS (aka Depth-First Search) is indeed the algorithm of choice for detecting them ... This problem is solved with a straightforward application of Depth-First search indeed $\endgroup$ Mar 10, 2020 at 16:34

1 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$.

  • $\begingroup$ What do you mean by "start vertex"? For example, if $G$ is a cycle of length 4, what vertex will be the "start" one? $\endgroup$ Mar 9, 2020 at 19:11
  • $\begingroup$ @alex07021998 I misread the question. See the update. $\endgroup$
    – Vladislav
    Mar 9, 2020 at 19:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.