#include "friend.h"
#include<bits/stdc++.h>
using namespace std;
int findSample(int n, int confidence[], int host[], int protocol[]){
vector<int>edges[n];
for (int i = 1; i < n; i++){
if (protocol[i] == 0){
//iam your friend
edges[i].push_back(host[i]);
}else{
edges[i] = edges[host[i]];
}
}
//bipirtite max match is congruent to Min Vertex cover
//because of konig's theorem
//max independent set is opposite of min vertex cover
vector<bool>used1(n, false);
vector<bool>used(n, false);
vector<int>to(n, -1);
int res = n;
for (int i = 0; i < n; i++){
for (int j : edges[i]){
if (to[j] == -1){
--res;
to[j] = i;
used1[i] = 1;
break;
}
}
}
function<int(int)>dfs = [&](int u){
if (used[u])return 0;
used[u] = 1;
for (int& x : edges[u]){
if (to[x] == -1 || dfs(to[x])){
to[x] = u;
return 1;
}
}
return 0;
};
for (int i = 0; i < n; i++){
if (!used1[i]){
used.assign(n, false);
res -= dfs(i);
}
}
return res;
}
