题目大意

给出一个有$n$个点和$m$条边的有向图，希望选择含有尽可能多点的点集，使得这个集合中的任意两个点互相无法到达

数据范围

$n\leqslant 100,m\leqslant 1000$

题解

按照题目条件，就是希望求出这个图的最大点独立集

根据独立集与覆盖集互补定理，现在问题化解为求出这个图的最小点覆盖集

可以用二分图最大匹配求出最小点覆盖集$ans$

则最大点独立集就是$result=n-ans$

关于独立集和覆盖集可以看这个

程序

#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#define For(i,l,r) for(int i=l;i<=r;i++)
using namespace std;

int map[205][205],vis[205],link[205];
int n,m,ans;

int check(int x){
    For(i,1,n)
        if ((!vis[i])&&map[x][i]){
            vis[i]=1;
            if ((!link[i])||check(link[i])){link[i]=x;return 1;}
        }
    return 0;
}

int main(){
    scanf("%d%d",&n,&m);
    For(i,1,m){
        int x,y;scanf("%d%d",&x,&y);
        map[x][y]=1;
    }
    For(k,1,n) For(i,1,n) For(j,1,n)
        map[i][j]|=map[i][k]&map[k][j];
    For(i,1,n){
        memset(vis,0,sizeof(vis));
        if (check(i)) ++ans;
    }
    printf("%d\n",n-ans);
    return 0;
}