*Given an undirected graph G=(N,A), where every vertex is colored with red or blue, and two red vertexes from N are: r and s.*

1) We want to verify the existence of a path from r to s containing only red vertexes. Write the pseudo code for an optimal time algorithm.

2) We want to verify in general the existence of a cycle in that graph that contains only red edges. Write the pseudo code for an optimal time algorithm.

1) We want to verify the existence of a path from r to s containing only red vertexes. Write the pseudo code for an optimal time algorithm.

2) We want to verify in general the existence of a cycle in that graph that contains only red edges. Write the pseudo code for an optimal time algorithm.

My solution:

I'm not looking for the code but just for any idea for the algorithm. I found a very

**rough**way to verify these conditions so would like to hear your opinion.

1) Start from r and keep on visiting only the red nodes (using some edge lists or whatever) through the connected edges, everytime writing something like "VISITED" switching from the previous state "UNEXPLORED". If there aren't unexplored red nodes anymore and s still hasn't been visited, there doesn't exist such a path.

2) Visit the whole graph through BFS until you get to a CROSS edge. If both of its nodes are red, choose one, save the state "START" and keep on visiting all the red nodes connected until you get to the "START", If at the end start node wasn't found, then change it to UNEXPLORED and start everything again from a different cross edge.

Would these ideas work? I'm not sure about the second but I think the solution for the first one isn't that bad.