Consider each person as a node on a graph. Two nodes are connected only when both persons like each other.
Now do any traversal of this graph to find the number of connected components. That should be the minimum no. of houses required. On Sun, May 29, 2011 at 9:17 PM, ross <[email protected]> wrote: > There are n persons. > You are provided with a list of ppl which each person does not like. > Determine the minm no. of houses required such that, in no house > 2 people should dislike each other. > > Is there a polynomial time solution exist for this? Or is this not > solvable at all? > > -- > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > To post to this group, send email to [email protected]. > To unsubscribe from this group, send email to > [email protected]. > For more options, visit this group at > http://groups.google.com/group/algogeeks?hl=en. > > -- Amit Jaspal. Men do less than they ought, unless they do all they can -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to [email protected]. To unsubscribe from this group, send email to [email protected]. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
