Only DFS? Or exist fast solution? Please help me

I call it adjusting...
First put them all into Group A
Then if there exits a person who have two enemies, throw them into another group.
It can be proved that you have to do this operation only twice. (from Group A to Group B, and then from Group B to Group A)

Thanks a lot, AC now

Edited by author 05.01.2010 05:03

I think your algo doesn't work on this test
6
3 2 3 4
3 1 3 4
1 1
2 1 5
2 4 6
1 5

first
A, A, A, A, A, A
then put 2 and 3 in the group B (child 1) and 4 and 6 (child 5)
A, B, B, B, A, B

for child 2 from group B, put 3 and 4 in the group A

A, B, A, A, A, B

So, for child 1, it's enemies 2 and 3 are in his group.

Where am i wrong?

If we do it only twice, we'll get WA at test like this.

18
3 2 4 5
3 1 3 6
3 2 7 8
3 1 9 10
3 1 11 12
3 2 13 14
3 3 15 16
3 3 17 18
1 4
1 4
1 5
1 5
1 6
1 6
1 7
1 7
1 8
1 8