In a tournament graph, how do I find whether there is a player who has dominated all the other players? What is the run-time of such algorithm?
Basically, I need to find if there is an element, from which I can reach to all the other elements, following the path of outlinks.
Clarification: Here; if 'a' beats 'b', and 'b' beats 'c', then a has dominated 'c'. Basically if 'a' beats 'c' directly OR indirectly, it has dominated 'c'. It might be possible that 'a' and 'b' have dominated each other indirectly, which is why the winner may or may not exist. There could also be more than one winners.
Tournament graph is a directed graph where each element has a directed edge with each of the rest of the elements. So there are n*(n-1)/2 directed edges, where n is the number of vertices(players). Wikipedia article on Tournament Graph
Let's call the original graph T
with N
vertices and M
edges. First compute the condensation of T
and let's call it G
. Every vertex v
of G
represents several vertices of T
; additionally, you can reach from any of this vertices to another in T
. Also, G
is a DAG. So, if there's only one vertex in G
with in-degree equal to 0 (let's call it v0
), that means that you can reach any vertex in the original graph starting from a vertex in v0
. If v0
corresponds to a single vertex in T
, then it is the vertex you are looking for already. The complexity is O(N+M)
.
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With