//用tarjan求出强连通分量，再将强连通分量的所有点缩为一个点
//具体的tarjan算法http://www.cnblogs.com/saltless/archive/2010/11/08/1871430.html
//然后重新建图，很容易想到剩下的是一个最小路径覆盖的题目
#include<iostream>
#include<cstdio>
#include<cstring>
#include<vector>
using namespace std;
const int maxn = 50100;
int low[maxn];
int dfn[maxn];
int vis[maxn];
int stack[maxn];
int instack[maxn];
int match[maxn];
int belong[maxn];
int top,step,num;
vector<int> vec_1[maxn];
vector<int> vec_2[maxn];
int dx[maxn*2],dy[2*maxn];
int n ,m;
void init()
{
step = top = num = 0;
memset(instack,0,sizeof(instack));
memset(low,0,sizeof(low));
memset(dfn,0,sizeof(dfn));
for(int i = 0;i <= n;i++)
{
vec_1[i].clear();
vec_2[i].clear();
}
}
void tarjan(int u)
{
stack[++top] = u;
instack[u] = 1;
low[u] = dfn[u] = ++step;
for(int i = 0; i < vec_1[u].size() ;i++)
{
int v= vec_1[u][i];
if(!dfn[v])
{
tarjan(v) ;
low[u] = min(low[u],low[v]);
}
else if(instack[v])
low[u] = min(low[u],dfn[v]);
}
if(low[u] == dfn[u])
{
num ++;
int v = 0 ;
while(u!=v)
{
v = stack[top--];
belong[v] = num;
instack[v] = 0;
}
}
}
int find(int start)
{
for(int i = 0;i < vec_2[start].size();i++)
{
int v = vec_2[start][i];
if(!vis[v])
{
vis[v] = 1;
if(match[v] == -1 || find(match[v]))
{
match[v] = start;
return 1;
}
}
}
return 0;
}
void Match()
{
memset(match, -1,sizeof(match));
int ans = 0;
for(int i = 1;i <= num ;i++)
{
memset(vis,0,sizeof(vis));
if(find(i))
ans++;
}
printf("%d\n",num - ans);
}
int main()
{
int T;
scanf("%d",&T);
while(T--)
{
scanf("%d%d",&n,&m);
init();
for(int i = 1;i <= m ;i++)
{
scanf("%d%d",&dx[i] ,&dy[i]);
vec_1[dx[i]].push_back(dy[i]);
}
for(int i = 1;i <= n;i++)
if(!dfn[i])
tarjan(i);
for(int i = 1;i <= m;i++)
{
int u = belong[dx[i]];
int v = belong[dy[i]];
if(u == v)continue;
vec_2[u].push_back(v);
}
Match();
}
return 0;
}
hdu 3861 强连通分量缩点+二分匹配求最小路径覆盖
原文：http://blog.csdn.net/cq_pf/article/details/44568449
