1
$\begingroup$

There are two parties A and B going on. Some people are going to party A, some are going to party B.

We are given instructions of the form

  • different 1 3, meaning that person 1 and person 3 are attending different parties
  • same 3 4,
  • different 4 5,

and then given a command tell 1 4 we have to answer if they are attending the same party or a different.

Like from above we can conclude that 1 and 4 must be attending different party as 1 and 3 are attending different and 3 and 4 attend the same.


My thoughts : Make a hash table for A and B given x and y determine which one belongs to which hashtable if any not present put it in the appropriate hashtable.

Not sure if this is an efficient algorithm for this.

I was wondering if we could build a graph from the given info and then we can answer any amount of questions like that.

$\endgroup$
2
$\begingroup$

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.

  1. 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.
  2. 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.
$\endgroup$
11
  • $\begingroup$ when you say neighbours you mean the vertex directly adjacent to a vertex ? I want to add one requirement for complexity. So input will be like a list of instructions followed by list of commands tell 1 3 tell 1 4 and it's required to run in O(m) time where m is the number of commands. That's confusing because the run time should depend upon the number of nodes in graph too $\endgroup$ Mar 28 at 11:30
  • $\begingroup$ In this case, $2\cdot m \geq n$ since you always receive one edge and two vertices. $\endgroup$
    – Pål GD
    Mar 28 at 11:45
  • $\begingroup$ Yes, the neighbors of a person are all persons that have an edge to that person. $\endgroup$
    – Pål GD
    Mar 28 at 11:45
  • $\begingroup$ Thanks a lot. That seems to be a perfect solution. Need some help understanding it. Here when you write n - is that the number of vertices ? and what exactly you refer m here . Also so suppose we have a path from a to b of odd length. That would mean that there are in different party. And if the path is of even length that would mean that they are in same party. So once you have a path for a and b you mentioned that add an edge Pi to Pi+2 but aren't Pi and Pi+2 in the same parties because of even number of edges between them Pi to Pi+1 to Pi+2. Did you mean add an edge from Pi to Pi+3 ? $\endgroup$ Mar 28 at 13:29
  • 1
    $\begingroup$ Check out the union-find data structure. The point is that you get amortized $O( \alpha (n)) = o(\log n)$ lookup for same. It won't give you $O(m)$ but $O(m \alpha(m))$ running time, but then again, I'm not sure linear is possible. $\endgroup$
    – Pål GD
    Mar 30 at 9:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.