[EM] Is River O(n^2 log n) worst case?

[Kristofer Munsterhjelm]

The electowiki says that determining the River winner is O(n^3) worst
case, but I think I've found a way to make it n^2 log n.

In River, you have a list like Ranked Pairs, but a new pairwise entry
A>B is only added if both:
	- it produces no cycle
	- B is not already defeated by someone else.

So start River by creating a boolean "already defeated" array of length
equal to the number of candidates, all initialized to false. Also
initialize a disjoint-set structure containing every candidate as a
separate set, and sort the pairwise preferences in order of magnitude.

This takes O(n), O(n) and O(n^2 log n) time respectively.

Then go down the pairwise preference list and for each pairwise victory
A>B, add it if the "already defeated" boolean for B is false and A and B
belong to different sets of the disjoint set structure. If both of these
properties hold, then:
	- Add A>B to the output list
	- Set B's already defeated boolean to true
	- Merge the sets containing A and B.

Determining whether A and B is in the same set takes O(alpha(n)) time,
and determining if the already-defeated boolean is set takes constant
time. The operations that are part of admitting A>B takes constant time,
constant time, and O(alpha(n)) time respectively, where alpha(n) is the
inverse Ackermann function; for all intents and purposes, it's constant.

My idea is that if A and B are in the same set, then either A beats
someone who beats B, or B beats someone who beats A. If it's the former,
then admitting A>B would mean make B twice defeated, which is not
allowed. If it's the latter, then admitting A>B would create a cycle,
which is not allowed either. So, unlike Ranked Pairs, we don't need to
know which is the case, because either situation implies A>B should not
be admitted. So a disjoint set structure suffices.

Finally, the winner is the candidate who is not defeated at the end of
the process. Finding who that is obviously comes out to O(n) due to the
defeat array.

Supposing I'm right, the total runtime comes out to:

O(n^2 log n) for the setup stage
O(n^2 alpha(n)) for the admission stage,

and since log(n) > alpha(n), O(n^2 log n) for the method as a whole.

Does that sound right?

(Here I thought I had found a cloneproof O(n^2) Condorcet method. But I
found out it's *just* in excess of that, because of that log factor...)

... actually, isn't this just Kruskal's algorithm?