I think, if the Graph is 2-colorable (i.e. Bipartite) trip can be arranged.
On 30 August 2012 09:43, ashish mann <[email protected]> wrote: > 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. > -- 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.
