将所有最大连通分量缩点，然后统计缩点后每个点的出度，出度为0的肯定就是了可是这个点可能是缩出来的，所以要记录这个点真正包含的点数。如果出度为0的点大于1个说明不存在
View Code 稍微尝试了一下stl的vector和stack #include#include #include #include #include #define maxn 10017 using namespace std; int low[maxn],dfn[maxn],val[maxn],out[maxn]; bool instack[maxn]; int belong[maxn]; int bcnt,index; int n,m; vector g[maxn]; stack s; void init() { for (int i = 0; i < maxn; ++i) { g[i].clear(); low[i] = dfn[i] = belong[i] = val[i] = out[i] = 0; instack[i] = false; } index = bcnt =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(low[i] == dfn[i]) { bcnt++; do { j = s.top(); s.pop(); instack[j] = false; belong[j] = bcnt; val[bcnt]++;//记录缩点后的点真正拥有的点 } while (j != i); } } void solve() { int count = 0,i,j; for (i = 1; i <= n; ++i) { if (!dfn[i]) tarjan(i); } for (i = 1; i <= n; ++i) { for (j = 0; j < g[i].size(); ++j) { int k = g[i][j]; if (belong[i] != belong[k]) out[belong[i]]++; } } int t = 0; for (i = 1; i <= bcnt; ++i) { if (!out[i]) { count++; t = i; } } if (count > 1) puts("0"); else printf("%d\n",val[t]); } int main() { //freopen("d.txt","r",stdin); int x,y,i; while (cin>>n>>m) { init(); for (i = 1; i <= m; ++i) { cin>>x>>y; g[x].push_back(y); } solve(); } return 0; }