等价性问题，给出的样例为 a->b的形式，问要实现全部等价（即任意两个可以互相推出），至少要加多少个形如 a->b的条件。
容易想到用强连通缩点，把已经实现等价的子图缩掉，最后剩余DAG。要推出一个方案，YY后取“出度为零”和“入度为零”的点数的较大值。
理由：假定出度为零的点数较多，即是我们通常意义上的树的形式（当然，DAG是图，这里只是类比）。
根可以推出其所有子孙，事实上任意一个点都可以推出其子孙，那么只要让该节点推出树根，就可以推出整棵树上所有的节点了。那么多棵树为什么不是相乘呢？，借题目中的范例，a->b，b->c，c->a，形成一个循环即可。
本质：给定一个有向图，问是否加上多少条边，使原图构成强连通。
#include<stdio.h>
#include<string.h>
#include<stack>
#include<algorithm>
using namespace std; const int MAXN=; struct Edge{
int v,next;
Edge(){}
Edge(int _v,int _next):v(_v),next(_next){}
}edge[MAXN]; int tol,head[MAXN];
int low[MAXN],dfn[MAXN],sccno[MAXN],scc_cnt,TT; stack<int >stk; void init()
{
tol=;
memset(head,-,sizeof(head));
} void add(int u,int v)
{
edge[tol]=Edge(v,head[u]);
head[u]=tol++;
} void dfs(int u)
{
int v;
dfn[u]=low[u]=++TT;
stk.push(u);
for(int i=head[u];i!=-;i=edge[i].next)
{
v=edge[i].v;
if(!dfn[v]){
dfs(v);
low[u]=min(low[u],low[v]);
}else if(!sccno[v]){
low[u]=min(low[u],dfn[v]);
}
}
if(low[u]==dfn[u]){
scc_cnt++;
do{
v=stk.top();
stk.pop();
sccno[v]=scc_cnt;
}while(v!=u);
}
} void tarjan(int n)
{
scc_cnt=TT=;
memset(low,,sizeof(low));
memset(dfn,,sizeof(dfn));
memset(sccno,,sizeof(sccno)); while(!stk.empty())
stk.pop();
for(int i=;i<=n;i++)
if(!dfn[i])
dfs(i);
} int main()
{
int T,n,m;
int a[MAXN],b[MAXN];
scanf("%d",&T);
while(T--)
{
scanf("%d%d",&n,&m); init();
for(int i=;i<m;i++)
{
scanf("%d%d",&a[i],&b[i]);
add(a[i],b[i]);
} tarjan(n); int in[MAXN],out[MAXN];
memset(in,,sizeof(in));
memset(out,,sizeof(out));
for(int i=;i<m;i++)
{
if(sccno[a[i]]!=sccno[b[i]]){
in[sccno[b[i]]]++;
out[sccno[a[i]]]++;
}
} int innum,outnum;
innum=outnum=;
for(int i=;i<=scc_cnt;i++)
{
if(!in[i])
innum++;
if(!out[i])
outnum++;
} if(scc_cnt==)printf("0\n");
else printf("%d\n",max(innum,outnum));
}
return ;
}