#include <bits/stdc++.h> #include "friend.h" using namespace std; // subtask 5 const int MAXN=1000; int left_of[MAXN], right_of[MAXN]; bool seen[MAXN]={false}, visited[MAXN]={false}; vector<int> adj[MAXN], adjtemp[MAXN]; void dfs(int x, int t, bool parity) { if (visited[x]) return; visited[x]=true; for (auto y : adjtemp[x]) { if (y==t) continue; if (parity==0) adj[x].push_back(y); else adj[y].push_back(x); dfs(y, x, (parity+1)%2); } return; } bool find_match(int index) { if (seen[index]) return false; seen[index]=true; for (int next : adj[index]) if (left_of[next]==-1) { left_of[next]=index; right_of[index]=next; return true; } for (int next : adj[index]) { int current_connection=left_of[next]; if (find_match(current_connection)) { left_of[next]=index; right_of[index]=next; return true; } } return false; } int findSample(int n, int confidence[], int host[], int protocol[]) { for (int i=1; i<n; i++) { if (protocol[i]==0) { adjtemp[host[i]].push_back(i); adjtemp[i].push_back(host[i]); } if (protocol[i]==1) for (auto x : adjtemp[host[i]]) { adjtemp[x].push_back(i); adjtemp[i].push_back(x); } } for (int i=0; i<n; i++) dfs(i, -1, 0); for (int i=0; i<n; i++) left_of[i]=-1; for (int i=0; i<n; i++) right_of[i]=-1; int matched=0; for (int i=0; i<n; i++) { for (int j=0; j<n; j++) seen[j]=false; if (find_match(i)) matched=matched+1; } return n-matched; }