Q. A company organizes two foreign trips for its employees yearly. Aim of
the trip is to increase interaction among the employees of the company and
hence company wants each of his employee to see new people on the trip and
not even a single person with whom he has worked in past. Therefore it is a
rule in company that in any of the trips, all the employees should be new
to each other and no two of them should have worked together in past.
Given the work history of each employee (which people he has worked with
sometimes in past), you have to tell whether all of the employees can be
accommodated within trips without violating the above rule or not. Each
employee is given a unique integer ID by which they are recognized. You can
also assume that each employee has worked with at least one other employee
in past.
*Note: *No employee can be in both trips and every employee must be part of
one trip.
*Example: *
i) Suppose the work history is given as follows: {(1,2),(2,3),(3,4)}; then
it is possible to accommodate all the four employees in two trips (one trip
consisting of employees 1& 3 and other having employees 2 & 4). Neither of
the two employees in the same trip have worked together in past.
ii) Suppose the work history is given as {(1,2),(1,3),(2,3)} then there is
no way possible to have two trips satisfying the company rule and
accommodating all the employees.
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
