I have a set $S$ of pairs $(x_1,x_2)$ with $x_1,x_2 \in X$ for some set $X$.
I want to know whether this defines a total relation on $X$. In other words, whether:
- If $(a,b)$ in $S$ and $(b,c)$ in $S$, then $(a,c)$ in $S$. (transitivity)
- Exactly one of $(a,b)$ and $(b,a)$ is in $S$ unless $a=b$, in which case they are both an element of $S$. (totality and antisymmetry)
Brute-force would take $O(|X|^3|S|)$ steps (I think), because there are $|X|^3$ triples $(a,b,c)$ and looking up whether something is an element of an array costs $O(|S|)$.