Determining whether a relation is the "union" of two other relations Given a relations $P$ and $Q$ on $S$, what are the most efficient algorithms to find whether the relation satisfy the constraints $P \cup Q = S \times S$ and $P \cap Q = \emptyset$?

If it helps, for my application the elements of $S$ are strings. Apologies if my question is not up to standard, this is my first question on Stack Exchange and it's been several years since I've done any formal math.
The following should suffice:

for each (x,y) in P:
    if (x,y) in Q, print "nope" and quit
for each (x,y) in Q:
    if (x,y) in P, print "nope" and quit
count the number of pairs in P and Q.
if this sums to |S|^2, output "yup, otherwise output "nope".


You could use any method.  For instance, you could compute $P \cup Q$ directly, then compute $P \cap Q$ directly (say, using mergesort-like methods), and check that each has the desired value.

All of these will have essentially the same asymptotic running time.