Party 115A (Graph Ques. ) Codeforces

Hello codechef !
can anyone explain me the test case of this question ?
Thanks in advance :slight_smile:

The problem is basically a hierarchical representation of employees.

Every employee will have a superior.
The test cases are given as:
First line will have N as number of employees. Then N subsequent line for i from 1 to N will represent the superior of employee i.
Testcase:

5
-1 (1 has no superior)
1 (2’s superior is 1)
2 (3’s superior is 2)
1 (4’s is 1)
-1 (5 doesn’t have any superior)

This makes the heirarchial representation as

Now as you don’t have to place any superior with his subordinate so you’ll have to keep everyone who is a superior of other in different set.

Consider the case for 1, 2, 3 keeping any two of them in one group is invalid as 1<-2 , 2<-3, 1<-3. So you’ll make 3 seperate groups for all three of them.
Now the remaining 4 and 5.
4 just has a superior 1 so we can keep it with any of 2 or 3.
5 has no superior so he can adjust in in any of the 3 groups formed so far.

Hope I’m not unclear.

1 Like

https://codeforces.com/contest/115/submission/74215798

1 Like

Thank you @light301 for a wonderful explanation :slight_smile:
now que is clear to me and i got AC :smiley:

1 Like