Hint

If we can solve the following problem fast enough, the original problem can be solved by solving this problem \(N\) times:

Can Player \(1\) be the unique winner? \(\cdots(*)\)

In the intended solution, \((*)\) is solved as a maximum flow problem.

We recommend you to try boiling down \((*)\) to the maximum flow problem by constructing graphs.

Answer

We will solve the following problem as a maximum flow problem.

Can Player \(p\) be the unique winner?

First, we may assume that Player \(p\) will win any players against which the result of the match has not been determined.
Let \(win\) be the number of Player \(p\)’s wins. If \(win=0\), then he cannot be the unique winner, so hereinafter we assume \(win \geq 1\).

Prepare vertices \(S,T,A_{i,j}( 1\leq i\lt j\leq N)\), and \(B_i (1\leq i \leq N)\).
\(S\) is the source, \(T\) is the sink, \(A_{i,j}\) represents the match between Players \(i\) and \(j\), and \(B_i\) represents Player \(i\).

Add the following edges with capacities \(1\).

• An edge \(S \rightarrow A_{i,j}\)

• For every match between Players \(i\) and \(j\),

  • If \(i\) won, add an edge \(A_{i,j} \rightarrow B_i\)
  • If \(j\) won, add an edge \(A_{i,j} \rightarrow B_j\)
  • If they have not have a match yet, add an edge \(A_{i,j} \rightarrow B_i\) and an edge \(A_{i,j} \rightarrow B_j\)

• Add \(win\) number of edges \(B_p \rightarrow T\)

• Add \((win-1)\) number of edges \(B_i(i\neq p) \rightarrow T\)

The maximum flow from \(S\) to \(T\) on this graph is \(\frac{N(N-1)}{2}\) if and only if Player \(p\) may be the unique winner.

The capacities of the edges on this graph are all \(1\), and the number of edges is \(O(N^2)\), so it can be solved in an \(O(N^3)\) time.

By solving the problem for each \(p=1,2,\ldots N\), the entire problem has been solved in a total of \(O(N^4)\) time.