缩点后求每个点的入度与出度，最后结果是max（入度为0的点的个数，出度为0的点的个数）；只要整个图形成强连通图就可以证明了。。
今天真二把tarjian模板写错了，贡献了好几次wa竟然没有检查出来。。。。唉。。。
View Code #include#include #include #include #include #define maxn 20007 using namespace std; int low[maxn],dfn[maxn],belong[maxn],in[maxn],out[maxn]; bool instack[maxn]; int bcnt,index; vector g[maxn]; stack s; int n,m; void init() { for (int i = 0; i < maxn; ++i) { g[i].clear(); low[i] = dfn[i] = belong[i] = out[i] = in[i] = 0; instack[i] = false; } bcnt = index = 0; } void tarjan(int i) { int j,k; low[i] = dfn[i] = ++index; s.push(i); instack[i] = true; for (k = 0; k < g[i].size(); ++k) { j = g[i][k]; if (!dfn[j]) { tarjan(j); low[i] = min(low[i],low[j]); } else if (instack[j]) { low[i] = min(low[i],dfn[j]); } } if (dfn[i] == low[i]) { bcnt ++; do { j = s.top(); s.pop(); instack[j] = false; belong[j] = bcnt; }while (j != i); } } int main() { int i,j,x,y,k; while (~scanf("%d%d",&n,&m)) { init(); if (m == 0) { printf("%d\n",n); continue; } for (i = 1; i <= m; ++i) { cin>>x>>y; g[x].push_back(y); } for (i = 1; i <= n; ++i) { if (!dfn[i]) tarjan(i); } if (bcnt == 1) { printf("0\n"); continue; } for (i = 1; i <= n; ++i) { for (j = 0; j < g[i].size(); ++j) { k = g[i][j]; if (belong[i] != belong[k]) { out[belong[i]]++; in[belong[k]]++; } } } x = 0; y = 0; for (i = 1; i <= bcnt; ++i) { if (!in[i]) x++; if (!out[i]) y++; } printf("%d\n",max(x,y)); } return 0; }