[Solution] Largest Family solution codechef

Largest Family solution codechef – A certain parallel universe has exactly NN people living in it.

The ii-th of these NN people claims that they are the parent of exactly AiAi of these NN people.

Table of Contents

[Solution] Largest Family solution codechef

However, some of these people might be lying — the ii-th person may be either telling the truth (in which case they have exactly AiAi children) or lying (in which case they can have any number of children).

It is known that each person has at most one parent. Further, as one would expect, it is not allowed for a person’s child to also be their ancestor.

What is the maximum possible number of truth-tellers in this universe?

Input Format

  • The first line of input will contain a single integer TT, denoting the number of test cases.
  • Each test case consists of two lines of input.
    • The first line of each test case contains a single integer NN, the number of people.
    • The second line of each test case contains NN space-separated integers A1,A2,,ANA1,A2,…,AN.

Output Format

For each test case, output on a new line the maximum number of people that can be telling the truth.

[Solution] Largest Family solution codechef

  • 1T41041≤T≤4⋅104
  • 1N31051≤N≤3⋅105
  • 0Ai<N0≤Ai<N
  • The sum of NN across all test cases won’t exceed 31053⋅105.

Subtasks

  • Subtask 1 (20 points):
    • 1T51≤T≤5
    • 1N201≤N≤20
  • Subtask 2 (80 points):
    • No further constraints.

Sample Input 1 

4
2
1 0
2
1 1
3
2 0 1
5
2 3 1 2 3

[Solution] Largest Family solution codechef

 

2
1
2
2

Explanation

Test case 11: Both people can be telling the truth, with the first person being the parent of the second.

Test case 22: If both people were telling the truth, they would be each others’ parents — and that is not allowed. Hence, at most one of them can be telling the truth.

Test case 33: The first and third people cannot be telling the truth at the same time. However, it is possible for the first and second people to be truthful — person 11 can be the parent of person 22 and person 33. Hence, the answer is 22.

Test case 44: There are several ways to pick 22 people to be telling the truth — for example,

  • The parent of person 22 and person 33 is person 11
  • The parent of person 11 and person 55 is person 44

in which case persons number 11 and 44 would be telling the truth.

However, it can be shown that it is impossible for any three of them to be simultaneously telling the truth.

For Solution

Click Here

Leave a Comment