How to efficiently determine whether a relation is total?
A good first step is to construct a certain matrix corresponding to your relation, which I will let you figure out. Constructing this matrix takes time $O(|X|^2 + |S|)$ (or just $O(|S|)$, depending on your exact model). Given this, you can check antisymmetry in time $O(|X|^2)$, and transitivity in time $O(|X|^3)$.

You can improve the running time of transitivity checking to $O(|X|^\omega)$, where $\omega$ is the matrix multiplication constant; I'll let you figure out how.