先强连通缩点，再就是二分匹配问题，最小路径覆盖
#include<stdio.h>
#include<stack>
#include<string.h>
using namespace std;
#define N 50001
#define inf 0x3fffffff
int n,m,OP;
int belong[N],dfs[N],low[N],ins[N],in[N],out[N],vis[N],link[N];
struct op
{
int end;
struct op *next;
}*e[100002],*E[100002];
void addeage(int x,int y)
{
struct op *q=new op;
q->end=y;
q->next=e[x];
e[x]=q;
}
void addeage1(int x,int y)
{
struct op *q=new op;
q->end=y;
q->next=E[x];
E[x]=q;
}
stack<int>Q;
int ans,idx;
void Tarjan(int x)//强连通
{
int v;
dfs[x]=low[x]=idx++;
Q.push(x);
ins[x]=1;
for(op *j=e[x];j;j=j->next)
{
if(dfs[j->end]==-1)
{
Tarjan(j->end);
low[x]=low[x]>low[j->end]?low[j->end]:low[x];
}
else if(ins[j->end]==1)
low[x]=low[x]>dfs[j->end]?dfs[j->end]:low[x];
}
if(low[x]==dfs[x])
{
ans++;
while(1)
{
v=Q.top();
Q.pop();
ins[v]=0;
belong[v]=ans;//缩点
if(v==x)break;
}
}
}
int find(int i)
{
for(op *j=E[i];j;j=j->next)
{
if(vis[j->end]==0)
{
vis[j->end]=1;
if(link[j->end]==-1||find(link[j->end])==1)
{
link[j->end]=i;
return 1;
}
}
}
return 0;
}
int main()
{
int i,j,x,y,z,t;
scanf("%d",&t);
while(t--)
{
scanf("%d%d",&n,&m);
OP=0;
for(i=0;i<=n;i++)
{
e[i]=NULL;
E[i]=NULL;
dfs[i]=-1;
ins[i]=0;
out[i]=0;
in[i]=0;
}
for(i=0;i<m;i++)
{
scanf("%d%d",&x,&y);
addeage(x,y);
}
ans=idx=0;
for(i=1;i<=n;i++)
{
if(dfs[i]==-1)
Tarjan(i);
}
for(i=1;i<=n;i++)
{
for(op *j=e[i];j;j=j->next)
{
if(belong[i]!=belong[j->end])
addeage1(belong[i],belong[j->end]);//建二分图
}
}
int sum=0;
memset(link,-1,sizeof(link));
for(i=1;i<=ans;i++)
{
memset(vis,0,sizeof(vis));
if(find(i)==1)
sum++;//最大匹配
}
printf("%d\n",ans-sum);
}
return 0;
}