Graph-Theory: Algorithm for finding the winner in the tournament schedule (if any)

Question

On the tournament schedule, how do I find if there is a player who dominated all the other players? What is the lead time for such an algorithm?

Basically, I need to find if there is an element from which I can contact all other elements, following the path of outgoing links.

Clarification: here; if "a" beats "b" and "b" beats "c", then a dominates "c". Basically, if “a” beats “c” directly or indirectly, it dominates “c”. It is possible that "a" and "b" will dominate each other indirectly, so the winner may or may not exist. There may also be more than one winner.

A tournament graph is a directed graph in which each element has a directed edge with each of the other elements. Thus, there are n * (n-1) / 2 directional edges, where n is the number of vertices (players). Tournament schedule Wikipedia article

Answer 1

Let us call the original graph T with vertices N and M edges. First, calculate the condensation T and call it G Each vertex v of G represents several vertices from T ; in addition, you can get from any of these peaks to the other in T In addition, G is a DAG. So, if in G there is only one vertex with a degree equal to 0 (let's call it v0 ), this means that you can reach any vertex in the original graph, starting from the vertex in v0 . If v0 corresponds to a single vertex in T , then this is the vertex already found. Complexity O(N+M) .

Answer 2

One way to do this is to take each vertex and perform a depth search with that vertex as the root. For each depth search, you check to see if you have visited all the other peaks. If so, the player who matches this top dominates all the players on the chart. If you are familiar with C ++, I can write a program here. The complexity of the time is ~ O (N ^ 3). Do you need a faster algorithm? N is the number of vertices

Answer 3

If there is a player who dominated all the others, then there is exactly one vertex v in the graph without incoming edges. Make DFS starting with v. If you can reach any other peak, then v is the dominant peak.

EDIT 1: As kaktusito suggested, we could condense the graph before applying DFS.

EDIT 2: It seems there is no need to explicitly calculate all related components, apply condensation, build a DAG, and find dominant vertices. Instead, here's a simpler solution:

First run DFS on the graph and find the node v with the highest end time. If the graph has winners, then v must be among them. Otherwise, there would be another vertex u such that v is reachable from u and has a later end time. Now, to find other winners, find all the nodes that are reachable from v in the transposed graph using DFS or BFS from v. The complexity of this algorithm is still O (V + E), but the implementation (and constant) is significantly simpler.