题目链接

某学校要召开一个舞会。已知学校所有 nn 名学生中，有些学生曾经互相跳过舞。当然跳过舞的学生一定是一个男生和一个女生。在这个舞会上，要求被邀请的学生中的任何一对男生和女生互相都不能跳过舞。求这个舞会最多能邀请多少个学生参加。

这道题就是二分图的模板，答案 $=$ 所有点数 $-$ 二分图的最大匹配。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
template<typename T>inline void read(T &FF){T RR=1;FF=0;char CH=getchar();for(;!isdigit(CH);CH=getchar())if(CH=='-')RR=-1;for(;isdigit(CH);CH=getchar())FF=(FF<<1)+(FF<<3)+(CH^48);FF*=RR;
}
template<typename T>void write(T x){if(x<0)putchar('-'),x*=-1;if(x>9)write(x/10);putchar(x%10+48);
}
const int MAXN=10010;
vector<int>V[MAXN];
int n,m,vis[MAXN],h[MAXN],ans,x,y;
bool dfs(int u){for(auto v:V[u]){if(vis[v])continue;vis[v]=1;if(h[v]==-1||dfs(h[v])){h[v]=u;h[u]=v;return true;}}return false;
}
int main(){memset(h,-1,sizeof(h));//编号从0开始read(n);read(m);while(m--){read(x);read(y);V[x].push_back(y);}for(int i=0;i<n;i++){memset(vis,0,sizeof(vis));if(dfs(i))ans++;}write(n-ans);return 0;
}