It will be difficult with your idea as you don't initially know which table to put a person in. For example will different 1 2 and different 3 4 have two solutions, namely $A = \{1, 3\}$ and $B = \{2, 4\}$, and also $A = \{1, 4\}$ and $B = \{2, 3\}$ (and symmetrically). When you get the information that different 2 3, you have now lost some crucial information that you need.
The answer is graphs.
A graph is bipartite if and only if it is two-colorable (if and only if it has no odd cycles).
You are creating a bipartite graph such that when there is an edge between two people then they attend different parties.
When the graph is connected, it is easy to say whether two people are in the same party or not: Given $u$ and $v$, if the shortest path from $u$ to $v$ has an even number of edges, they are in the same party, if it has an odd number of edges, they are in different parties.
The command different u v simply adds the edge between $u$ and $v$.
However, the command same u v is slightly worse since you need to record the fact that they don't have an edge.
I would do the following.
- If $u$ or $v$ have neighbors, add edges from $u$ to $N(v)$ and/or $v$ to $N(u)$. One is enough, but you can also make it complete. This is a space/time tradeoff.
- If neither $u$ nor $v$ have neighbors, construct an artifical vertex $x_{uv}$ and connect both $v$ and $u$ to $x_{uv}$. If $u$ or $v$ later get a different command, say
different v w, you can remove $x_{uv}$, or identify $x_{uv}$ and $w$ (merge the vertices and their neighborhoods).
Complexity:
different a b → $O(1)$. Add edge in constant time. Check if $a$ or $b$ has an $x$-neighbor takes $O(1)$ time, delete that vertex takes time $O(1)$. Add at most two edges after $x$ deleted.same a b → $O(1)$. Check existence of neighborhood, if so, add two edges in constant time. Otherwise, create $x$ vertex and add two edges in constant time.tell a b → $O(n + m) = O(m)$ with a single BFS search. When you get the path $P$ you can add edge from $P_i$ to $P_{i+2}$ for all $i$; that could lower the future searching time.
