知识点：强连通分量、缩点、再加用最大二分匹配求最小路径覆盖。
bug处：突然发现没有模板自己敲的时候巨多的错误，比如说求强连通分量时连反向表都没有建，再比如说求二分匹配的时候在一个图里表示两个图的时候应是flag标记数组写不好，注意是在if(0== flag[b[i][j]])之后写flag[b[i][j]] = 1;因为此时是j点在交错路上面。最后是没有想清楚那个最小路径覆盖的数目应该是缩点之后的有向无环图的点的个数，即强连通分量的个数减去最大匹配数。
思维：觉得还是知识点懂得太少了，并且现场有点怕，不敢去啃这个题目，我觉得比较好的策略是我们把简单题目做完之后就选定一道题目，啃，我觉得自己这方面没有做好，随着我们知识系统的完善，我觉得我们应该每一次都努力的啃一道难题出来。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<vector>
using namespace std;
#define max 5010
int n,m;
vector<int> a[max],b[max],adjact[max];
int flag[5010];
int id[max];
int result[max];
int pipe[max];
void initone()//初始化注意建反向图
{
memset(a,0,sizeof(a));
memset(adjact,0,sizeof(adjact));
scanf("%d%d",&n,&m);
for( int i=1; i<=m; i++ )
{
int aa,bb;
scanf("%d%d",&aa,&bb);
a[aa].push_back(bb);
adjact[bb].push_back(aa);
}
}
void vistone(int i,int &sig)//第一次深度优先搜索，注意其中的id为改点的最后离开时间，所以id的赋值应该要放到递归的后面，注意sig的&符号
{
flag[i] = 1;
int num = a[i].size();
for( int j=0; j<num; ++j )
{
if( 0 == flag[a[i][j]] )
vistone(a[i][j],sig);
}
id[++sig] = i;
return;
}
void visttwo(int i,int sig)//注意此时用到的图为反向之后的图
{
result[i] = sig;
flag[i] = 1;
int num = adjact[i].size();
for( int j=0; j<num; ++j )
{
if( 0 == flag[adjact[i][j]] )
visttwo(adjact[i][j],sig);
}
return;
}
int f()//用来求强连通分量，首先对原图dfs一次，记住每个点的离开时间，然后按离开时间从大到小再对反向图dfs一次，注意第二次的sig要自增。
{
memset(id,0,sizeof(id));
memset(flag,0,sizeof(flag));
int sig = 0;
for( int i=1; i<=n; ++i )
{
if( 0 == flag[i] )
vistone(i,sig);
}
sig = 0;
memset(flag,0,sizeof(flag));
for( int i=n; i>=1; --i )
{
if( 0 == flag[ id[i] ] )
{
visttwo(id[i],++sig);
}
}
return sig;
}
void inittwo( )//建缩点之后的图，注意此时建成之后的图中的点应该是强连通分量。所以注意建图过程中的赋值。
{
memset(b,0,sizeof(b));
for( int i=1; i<=n; i++ )
{
int num = a[i].size();
for( int j=0; j<num; ++j )
{
if( result[i] != result[a[i][j]] )
b[result[i]].push_back(result[a[i][j]]);
}
}
return;
}
bool find(int i)//注意find函数中的flag赋值处，pipe数组的赋值，只要单向赋值。
{
int num = b[i].size();
for( int j=0; j<num; ++j )
{
if( 0 == flag[b[i][j]] )
{
flag[b[i][j]] = 1;
if( 0 == pipe[b[i][j]] || find( pipe[b[i][j]] ) )
{
pipe[b[i][j]] = i;
return true;
}
}
}
return false;
}
int hungary(int ss)//注意每一次调用find之前都要将flag数组中的元素赋为0.
{
int sum = 0;
memset(pipe,0,sizeof(pipe));
for( int i=1; i<=ss; i++ )
{
memset(flag,0,sizeof(flag));
if( find(i) )
sum++;
}
return sum;
}
int main()
{
int t;
scanf("%d",&t);
while( t-- )
{
initone();
int ss = f();
inittwo();
int nn = hungary(ss);
printf("%d\n",ss-nn);
}
return 0;
}