Graphs bootcamp doubt


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



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.



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?