You are planning the seating arrangement for a meeting given

You are planning the seating arrangement for a meeting given a list of guests, V. Suppose you are also given a lookup table T where T[u] for u V is a list of guests that u knows. If u knows v, then v knows u. You are required to arrange the seating such that any guest at atable knows every other guest sitting at the same table either directly or through some other guests sitting at the same table. For example, if x knows y, and y knows z, then x,y,z can sit at the same table. Describe an efcient algorithm that, given V and T, returns the minimum number of tables needed to achieve this requirement.

Solution

Follow a student relations out to two edges, get a graph:

All the students in the same subgraph have to be separated, so the minimum number of tables is one for each students in the largest group - in this example the largest subgraph is r-w-x-y-z, so 5 tables.

Analyze the running time of your algorithm.

Analysis: Fine on any computer more powerful than a snowglobe.

Not sure. Best case: students have no friends - linear with respect to number of students. O(n). Worst case: every student is friends with every other student, then it does lookups for every student for every student, so O(n^3).