Some people in n groups, hates from each others. the hates relation are symmetric. (a hates b, b hates a, also). suppose we know list of all people that hates from others. (which one hates from which ones...). we want to divide these people into two groups such that no one in each group hates from others in the same group. which is the fast algorithm that detect and solve this problem is :1) O(N^2)2) O(N^3)3) O(N^4)4) there is no poly time solution.anyone could help me to solve this 2012 Local Informatic Olympiad of China? 
Hates Pepole Nice Algorithm
algorithms;assignment problem;algorithm design
This is equivalent to check if the hate graph is bipartite. Which can be done in linear time with respect to number of edges. Thus $O(n^2)$.