Patras

My definitive solutions that are OK: 1) OK 2) First create a graph made of red nodes only, then look for the existence of CROSS edges. If you don't know what a cross edge is: We used to call CROSS the edges that during a BFS bring you from the node you're visiting to a node that has already been visited. It's due to the fact that these edges weren't still visited but their opposit nodes were. If you try to watch a graph in this condition you see that these are the edges that shouldn't be in a tree, because they would connect two sibilings (or children) forming a cycle.

Hi everybody! I'm in trouble solving this problem: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. 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