这道题目要求我们找到在有向无环图（DAG）中，最少需要多少个伞兵才能访问所有节点，且每个节点只能被一个伞兵访问。伞兵可以从任意节点出发，沿着有向边移动。

关键观察

有向无环图（DAG）的性质：由于图中没有环，我们可以对图进行拓扑排序。

路径覆盖问题：题目可以转化为最小路径覆盖问题，即在DAG中用最少的路径覆盖所有节点。

二分图匹配：最小路径覆盖可以通过将原图转换为二分图，然后求解二分图的最大匹配来解决。

转换方法

将原图的每个节点拆分为两个部分：左部分和右部分。

对于原图中的每条边 u → v u→v，在二分图中连接左部分的 u u 和右部分的 v v。

最小路径覆盖数 = 原图节点数 - 二分图的最大匹配数。

算法步骤

构建二分图：将原图的节点拆分为两部分，并根据原图的边建立二分图的边。

匈牙利算法：在二分图上运行匈牙利算法，找到最大匹配。

计算最小路径覆盖：用节点数减去最大匹配数，得到最小路径覆盖数。

#include<cstdio>
#include<cstring>
#include<cctype>
using namespace std;
const int maxn=1001;
inline int read(){
    int X=0,w=0;char ch=0;
    while(!isdigit(ch)) {w|=ch=='-';ch=getchar();}
    while(isdigit(ch)) X=(X<<3)+(X<<1)+(ch^48),ch=getchar();
    return w?-X:X;
}
int n,m,e;
bool vis[maxn],a[maxn][maxn]={0};
int shu[maxn]={0};
bool dfs(int i){
    for(int j=1;j<=m;j++){
        if(a[i][j]&&!vis[j]){
            vis[j]=1;
            if(!shu[j]||dfs(shu[j])){
                shu[j]=i;
                return 1;
            }
        }
    }
    return 0;
}
int main(){
    int t=read();
    while(t--){
    memset(a,0,sizeof(a));
    memset(shu,0,sizeof(shu));
    int ans=0;
    m=n=read();
    e=read();
    for(int i=1;i<=e;i++){
        int u=read();
        int v=read();
        if(u>n||v>m) continue;
        a[u][v]=1;
    }
    for(int i=1;i<=n;i++){
        memset(vis,0,sizeof(vis));
        if(dfs(i))ans++;
    }
    printf("%d\n",n-ans);
    }
    return 0;
}