预处理传递闭包同”可达性统计”的拓扑排序+$bitset$做法一致,速度比朴素Floyd要快一些
总的时间复杂度$O(\frac{nm}{64}+n^2)$
#include <cstdio>
#include <bitset>
#include <queue>
#include <cstring>
#include <vector>
#include <algorithm>
using namespace std;
const int N=205,M=30005;
int n,m,u,v,x,y,s,ans,k,match[N];
bool ok[N];
bitset<N>f[N];
int deg[N],topo[N],cnt;
void toposort(){
queue<int>q;
for(int i=1;i<=n;i++){
if(!deg[i])q.push(i);
}
int k,v;
while(!q.empty()){
k=q.front();q.pop();
topo[++cnt]=k;
for(v=1;v<=n;v++){
if(!f[k][v]||k==v)continue;
deg[v]--;
if(!deg[v]){
q.push(v);
}
}
}
}
vector<int>g[N];
bool dfs(int u){
for(int v=1;v<=n;v++){
if(!f[u][v]||ok[v]||u==v)continue;ok[v]=1;
if(!match[v]||dfs(match[v])){
match[v]=u;return 1;
}
}
return 0;
}
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)f[i][i]=1;
while(m--){
scanf("%d%d",&u,&v);
f[u][v]=1;deg[v]++;g[u].push_back(v);
}
toposort();
for(int I=n,i;I>=1;I--){
i=topo[I];
for(int j=0,v;j<g[i].size();j++){
v=g[i][j];
f[i]|=f[v];
}
}
for(int i=1;i<=n;i++){
memset(ok,0,sizeof ok);
if(dfs(i))ans++;
}
printf("%d",n-ans);
return 0;
}