-3
$\begingroup$

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?

Improve this question
$\endgroup$
2
  • 1
    $\begingroup$ What have you tried? Where did you get stuck? We want to help you with your specific problems, not just solve your contest problem for you. However, as it is we don't know what your specific issue is and thus how to help. See here for a relevant discussion. If you are uncertain how to improve your question, why not ask around in Computer Science Chat? $\endgroup$
    – D.W. ♦
    Commented Feb 12, 2015 at 12:39
  • $\begingroup$ Hint: König's theorem. $\endgroup$
    – Raphael
    Commented Feb 12, 2015 at 13:06

1 Answer 1

Reset to default
0
$\begingroup$

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)$.

Improve this answer
$\endgroup$
0

Not the answer you're looking for? Browse other questions tagged or ask your own question.