Question

In a class room everyone is very friendly and has bonded with others in a short span of time. During the exams, students will sit along with their friends and will write the exams, which actually resulted in the finding that only a few members in the batch are good at studies and others are not. After getting several complaints from the staff members, the Principal has agreed to change the sitting pattern during the exams for which she has formed a committee. Using a spy, committee was able to get a list of close friends for all the students in the class. Now using this list they want to identify two groups of people such that a person in one group must not be a friend to any other in the same group. Your task is to help the committee.

Answer 1

Answer on Question #60893, Programming & Computer Science / C++

In a class room everyone is very friendly and has bonded with others in a short span of time. During the exams, students will sit along with their friends and will write the exams, which actually resulted in the finding that only a few members in the batch are good at studies and others are not. After getting several complaints from the staff members, the Principal has agreed to change the sitting pattern during the exams for which she has formed a committee. Using a spy, committee was able to get a list of close friends for all the students in the class. Now using this list they want to identify two groups of people such that a person in one group must not be a friend to any other in the same group. Your task is to help the committee.

Solution:

Lets $S_1, S_2, \ldots, S_n$ – all students.

$F(S_{i})$ – the set of close friends of student $S_{i}$. Obviously if this student belongs to the one group, all his close friends (i.e. all elements from $F(S_{i})$) must belong to the other group.

In our algorithm we will mark the student in three colors:

"white" – student don't belong to any of 2 groups yet; all students initially are white.

"yellow" – student belongs to any group but he has at least one white friend (i.e. he has friend that is not placed to any group yet).

"red" – student belongs to any group and ALL his close friends are marked red or yellow (i.e. all his friends are already placed to another group).

Algorithm:

1. If there exist any white student? If no, the algorithm is over and all students belongs to groups. If yes (first time of course at least one white student exists) then place this white student to the 1st group AND mark him yellow.
2. For all yellow students Sk do the following:
   2.1. Place all white students from F(Sk) to another group (if Sk belongs to 1st group then place F(Sk) to 2nd, and vice versa), and mark them yellow.
   2.2. If it is impossible to place at least one student from F(Sk) to group because he already has close friends there, then the problem has no solution, shut down the algorithm.
   2.3. Mark Sk in red.
3. If there exist any yellow student? If no (all red or white), then go to step 1. If yes, then go to step 2.

http://www.AssignmentExpert.com