Graphs bootcamp doubt

#1

My doubt is in Graphs boot camp, there is a question on teams A and B as follows :

Suppose you were given a list of the outcomes of matches between pairs of teams, with each outcome being a win or loss. A natural question is as follows: given teams A and B, is there a sequence of teams starting with A and ending with B such that each team in the sequence has beaten the next team in the sequence?

In the code, there is elif curr in visited . I am confused what is this check for? I thought initially it was cycles but for cycles you need 3 colors or you need add to path and remove later. Doubt: what is this check elif curr in visited doing

0 Likes
#2

Hi @abhigenie92

I partly agree with your question.

Since this is a directed graph, I also agree that 3 colors is needed to detect cycles. As far as I understand, 2 colors would be enough if it were undirected. (2 colors = using visited notion)

I suppose using 2 colors on directed graph detects forward or back edges. A back edge means a cycle although a forward edge does not. So using 2 colors on a directed graph might detect a cycle but also might detect a forward edge.

Since this question is only about finding “a” path I suppose it doesn’t matter whether we detect a forward edge or back edge. If we were interested in finding the shortest sequence etc. then we needed to differentiate between forward and back edges, because a forward edge might give us a shorter(alternative) path so we’d like to be able to detect forward edges separately in that case.

@tsunghsienlee @abhigenie92 I’d love to hear your feedback on these.

0 Likes
#3

I’m confused about time and space complexity of this question. It is stated as O(E) in the book. Shouldn’t it be O(V + E) where V is the number of teams?

0 Likes