题意：给我们一个图，问我们最少能把这个图分成几部分，使得每部分内的任意两点都能至少保证单向连通。
思路：使用tarjan算法求强连通分量然后进行缩点，形成一个新图，易知新图中的每个点内部的内部点都能保证双向连通，而新图中的点都是单向无环的，这个时候题目中要求的划分部分的条件，其实就是求最短路径覆盖（需要好好想一想），最短路径覆盖 = 结点个数 - 最大匹配值。
这个题我当时把j写成了i，就这么一个小地方，找了快20分钟，还死活发现不了。。真是晕死了～
最后我想总结一下这个题：
这个题很巧妙的把割点和二分图巧妙的结合了在一起，最后变成了最小路径覆盖问题，我就把我对最短路径覆盖的理解说一下吧：
最短路径覆盖，针对有向图而言，是找到最少的路径使覆盖所有的点，每个点的入度与出度最多是1，他的计算方法是 最短路径覆盖 = 结点个数 - 最大匹配值。
证明： 如果有n个点，0个匹配，那我们就有n条路径（一个单独的点也要被看作一条路径），当我们找到一个u和v的匹配的时候，我们需要的路径就少一，以此类推，就证明出了以上结论。
我在观察匹配算法的深搜树的时候发现了，我并没有去按照分两边集合的方式去考虑，而是按照父亲优先让出的原则去思考的，这个想法基于每个点只能最多有一个入度和出度，而且在深搜的过程中，每次直接匹配或迭代匹配都会使结果加1，但是迭代匹配有可能进行进行多次，但结果只加了1，其实是后来在的遍历中计算了结果，这也是为什么vis数组必须清空的原因之一。在匹配过程中我们并不关心匹配的方案，只关心匹配的最大数值，同一个值有可能对应多条匹配方案是当然的，但在二分图的题目中，很少有要求输出方案的，有的话也是随便输出一条，那直接输出我们随机匹配的match就好了～（仅代表个人看法）。
#include<iostream>
#include<cstdio>
#include<stack>
#include<cstring>
using namespace std;
#define maxn 5050
struct EDGE
{
int to,nxt;
} edge[maxn*];
EDGE newmap[maxn*];
int head[maxn],low[maxn],dfn[maxn],id[maxn],newhead[maxn];
int vis[maxn],match[maxn];
int tot,sum,tot1;
stack <int> s;
void init()
{
memset(dfn,,sizeof(dfn));
memset(low,,sizeof(low));
memset(id,,sizeof(id));
memset(head,-,sizeof(head));
memset(newhead,-,sizeof(newhead));
tot = ,sum = ;
tot1 = ;
while(!s.empty()) s.pop();
}
void add_edge(int x,int y)
{
newmap[tot1].to = y;
newmap[tot1].nxt = newhead[x];
newhead[x] = tot1++;
}
void tarjan(int u)
{
s.push(u);
dfn[u] = low[u] = ++tot;
for(int i = head[u]; i != -; i = edge[i].nxt)
{
int v = edge[i].to;
if(!dfn[v])
{
tarjan(v);
low[u] = min(low[u],low[v]);
}
else if(!id[v])
{
low[u] = min(low[u],dfn[v]);
}
}
if(low[u] == dfn[u])
{
sum++;
while(!s.empty())
{
int num = s.top();
s.pop();
id[num] = sum;
if(num == u) break;
}
}
return;
}
bool Find(int u)
{
for(int i = newhead[u]; i != -;i = newmap[i].nxt)
{
int v = newmap[i].to;
if(!vis[v])
{
vis[v] = ;
if(match[v] == - || Find(match[v]))
{
match[v] = u;
return true;
}
}
}
return false;
}
int erfen()
{
int ans = ;
memset(match,-,sizeof(match));
for(int i = ;i <= sum;i++)
{
for(int j = ;j <= sum;j++) vis[j] = ;
if(Find(i)) ans++;
}
return ans;
}
int main()
{
int t,n,m,x,y;
scanf("%d",&t);
while(t--)
{
scanf("%d%d",&n,&m);
init();
for(int i = ; i < m; i++)
{
scanf("%d%d",&x,&y);
edge[i].to = y;
edge[i].nxt = head[x];
head[x] = i;
}
for(int i = ;i <= n;i++)
{
if(!dfn[i])
tarjan(i);
}
for(int i = ;i <= n;i++)
{
int u = i;
for(int j = head[u];j != -;j = edge[j].nxt)
{
int v = edge[j].to;
if(id[u] != id[v])
{
add_edge(id[u],id[v]);
}
}
}
int ans = erfen();
printf("%d\n",sum-ans);
}
return ;
}