You are planning the group seating arrangement for a open book test given a list of students, V from different schools to participate. Assuming the fact that students who are known to each other directly or indirectly will probably cheat more as compared to unknown people sitting together.
Suppose you are also given a lookup table T where T[u] for u ? V is a list of students that u knows. If u knows v, then v knows u. You are required to arrange the seating such that any student at a table doesn't knows any other student sitting at the same table either directly or through some other student 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 efficient algorithm that, given V and T, returns the minimum number of tables needed to achieve this requirement. Analyze the running time of your algorithm.

• We can construct an undirected graph G = (V, E) with guests as vertices,
  and an edge between two vertices means the two guests know each other. Table T
  represents the adjacency lists for the vertices. Two guests can sit at the same table if
  there is a path between them. If we start from one vertex s and search the graph using
  breadth-first search (BFS) or depth-first search (DFS), all the guests that are reachable
  from s can sit at the same table, and additional tables are needed for vertices that are
  unreachable from s.
  Hence, to find the minimum number of tables, we can iterate through s ∈ V . If
  s is not visited, increment the number of tables needed and call DFS-VISIT(s, T)
  or BFS(s, T), marking vertices as visited during the traversal. Return the number
  of tables needed after iterating through all the vertices. This problem is equivalent to
  finding the number of connected components in the graph. The running time is Θ(V +
  E) because every vertex or edge is visted exactly once. Below is the pseudocode.
  NUM-TABLES(V, T)
  1 visited = {}
  2 n = 0
  3 for s ∈ V
  4 if s ∈/ visited
  5 n = n + 1
  6 add s to visited
  7 DFS-VISIT(s, T, visitied)
  8 return n
  DFS-VISIT(u, T, visitied)
  1 for v ∈ T[u]
  2 if v ∈/ visited
  3 add v to visited
  4 DFS-VISIT(v, T, visited)
• 9 years agoHelpfull: Yes(0) No(0)