## Largest Family Codechef Solution | LARGEFAM | (100/100) FULL | Codechef July Lunchtime | AC Code

A certain parallel universe has exactly

The

However, some of these people might be lying — the

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
T , 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
N the number of people. - The second line of each test case contains
N space-separated integersA1,A2,…,AN

### Output Format

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

### Sample Input 1 * *

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

### Sample Output 1 * *

```
2
1
2
2
```

` ````
```#include
#define ll long long
using namespace std;
void solve()
{
ll ok = 1, n;
if (ok != 1)
{
ll ji = 0;
}
else
{
cin >> n;
}
vector x;
ll z = 0;
for (ll i = 0; i < n; i++)
{
ll y;
cin >> y;
if (y == 0)
z++;
else
x.push_back(y);
}
sort(x.begin(), x.end());
for (ll i = 0; i < z; i++)
x.push_back(0);
ll o = 0, p = 1;
for (ll i = 0; i < n; i++)
{
int f = 1;
for (ll k = 0; k < x[i]; k++)
{
if (p < n)
p++;
else
{
f = 0;
break;
}
}
o += f;
}
cout << o << endl;
}
int main()
{
#ifndef ONLINE_JUDGE
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#endif
ios_base::sync_with_stdio(false);
cin.tie(NULL);
ll T;
cin >> T;
while (T--)
{
solve();
}
return 0;
}

## 0 Comments