#include <bits/stdc++.h> #include "friend.h" using namespace std; #define endl '\n' #define ll long long #define all(x) x.begin(), x.end() vector<int> g[1005]; bool visited[1005]; int p[1005], col[1005]; int dfs(int n) { for (auto x : g[n]) { if (visited[x]) continue; visited[x] = 1; if (p[x] == -1 || dfs(p[x])) { p[x] = n; return 1; } } return 0; } int findSample(int n, int confidence[], int host[], int protocol[]) { memset(p, -1, sizeof(p)); for (int i = 1; i < n; i++) { if (protocol[i] == 0) { g[host[i]].push_back(i); g[i].push_back(host[i]); col[i] = col[host[i]] ^ 1; } else { for (auto x : g[host[i]]) { g[i].push_back(x); g[x].push_back(i); } col[i] = col[host[i]]; } } int ans = n; for (int i = 0; i < n; i++) { if (col[i] == 0) { memset(visited, 0, sizeof(visited)); ans -= dfs(i); } } return ans; }