Interview Question
Country: United States
Super!... Draw undirected edge between two nodes where one people dislike other..
modify the adjacency matrix in which you have to set 1 where the value is 0 and vice versa
draw the graph again and now, no. of connected graph gives minimum number of home
This approach is completely invalid. Suppose I have 3 people, and 1 dislikes 3. The inversion of that graph is still 1 connected component. This problem is the same as graph coloring, which is NP-complete.
Suppose the dislike graph forms two disjoint sets, in this case the inverse graph is always a connected(so every node is taken into a room).
construct the Graph like this:set a edge between the two people who dislike each other.We can consider : if A dislikes B,it means that B dislikes A too.Then the minimum number of the homes is the minimum color number of the graph.
- notbad July 17, 2012