题目大意：
在数学中，我们常常需要完成若干个命题的等价性证明。比如，有4个命题a,b,c,d，我们证明a↔b,然后b↔c，最后c↔d。注意每次证明都是双向的，因此一共完成了6次推导。另一种方法是a→b，然后b→c，接着c→d，最后d→a，只需4次。现在你的任务是证明n个命题全部等价，且你的朋友已经为你做出了m次推导（已知每次推导的内容），你至少还需要做几次推导才能完成整个证明？
先tarjan一遍求出强连通分量，缩点，统计每个点的出入度。设有a个节点入读为0，b个节点出度为0，则答案就是max(a,b)。
代码：
#include<iostream> #include<cstdio> #include<cmath> #include<vector> #include<string.h> using namespace std; vector<int>g[20001]; int n,m,t,i,j,x,y,dfn[20001],dfs_clock,low[20001],in0[20001],out0[20001],c[20001],a,b,l,f[20001],cnt; void dfs(int u){ dfn[u]=low[u]=++dfs_clock; c[++l]=u; for(int i=0;i<g[u].size();++i) if(!dfn[g[u][i]]){ dfs(g[u][i]); low[u]=min(low[u],low[g[u][i]]); }else if(!f[g[u][i]])low[u]=min(low[u],dfn[g[u][i]]); if(low[u]==dfn[u]){ cnt++; while(c[l]!=u)f[c[l--]]=cnt; f[c[l--]]=cnt; } } int main() { scanf("%d",&t); for(int u=0;u<t;++u){ scanf("%d%d",&n,&m); for(i=1;i<=n;++i)g[i].clear(); for(i=1;i<=m;++i){ scanf("%d%d",&x,&y); g[x].push_back(y); } memset(dfn,0,sizeof(dfn)); memset(low,0,sizeof(low)); memset(in0,0,sizeof(in0)); memset(out0,0,sizeof(out0)); memset(f,0,sizeof(f)); memset(c,0,sizeof(c)); a=0;b=0;l=0;cnt=0;dfs_clock=0; for(i=1;i<=n;++i)if(!dfn[i])dfs(i); for(i=1;i<=n;++i) for(j=0;j<g[i].size();++j) if(f[g[i][j]]!=f[i]){ in0[f[g[i][j]]]++; out0[f[i]]++; } for(i=1;i<=cnt;++i){ if(!in0[i])a++; if(!out0[i])b++; } if(cnt==1)printf("0 ");else printf("%d ",max(a,b)); } return 0; }