CareerCup

What is the expected output?

What is the input/output and the problem ?

Bi-partite graph

Cant we use two dimensional bit array?

// basically a node(Person) having his name and an array of pointers pointing to the Person object of other group if it has punched that guy. So basically a graph.

Person{
String Name;

Person punchedPerson[];


}

For in put we can use matrix and for the output it will be best if use graph.

1. Traverse the whole list once and find the number of participants, say n.
{A1,A2,A3,...An}
2. Create an array of n elements; initially all the values are 0. Each array element represents Ai.
3. For the first person, say A1. put Array[1] =1.
4. While any of the array element is 0, follow steps 5,6 and 7.
5. If 'Ai punches Aj' , and exactly one of(Array[i],Array[j]) is Not 0
then both are in different groups. So modify the array value accordingly.
like, A1 punches A4, and Array[1] is 1 and Array[4] is 0 then put -1 for Array[4].
6. Else if Ai value and Aj value are 0, continue.
7. if Ai and Aj are same (both 1 or both -1) then the INPUT IS WRONG. Return.
8. Print all A[i] which are 1, as First group. All a[i] which are -1 are second group.

stack