唉＝ ＝这道题我都想到了tarjan缩点，但是没有想到最后一步啊＝ ＝我们很容易想到反向建边然后缩点，这时候我们看由多少个联通块的入度为0，如果为1个，那就输出这个块的大小，否则输出0；
#include#include #include #include using namespace std;const int maxn = 10010;const int maxe = 50010;struct edge { int t; edge* next;}e[maxe * 2], *head[maxn]; int ne = 0;int n, m;void addedge(int f, int t) { e[ne].t = t, e[ne].next = head[f]; head[f] = e + ne ++;}void read() { scanf("%d%d", &n, &m); for(int i = 1; i <= m; ++ i) { int u, v; scanf("%d%d", &u, &v); addedge(v, u); }}int dfs[maxn], back[maxn];int s[maxn], top = 0, Index = 0;bool vis[maxn]; int num = 0;int size[maxn];int belong[maxn];void tarjan(int now) { dfs[now] = back[now] = ++ Index; vis[now] = true; s[++ top] = now; for(edge* p = head[now]; p; p = p-> next) { if(!dfs[p-> t]) tarjan(p-> t), back[now] = min(back[now], back[p-> t]); else if(vis[p-> t] && back[now] > dfs[p-> t]) { back[now] = dfs[p-> t]; } } if(dfs[now] == back[now]) { ++ num; while(1) { belong[s[top]] = num; size[num] ++; vis[s[top]] = false; if(s[top] == now) break; top --; } top --; }}int f[maxn]; int in[maxn];bool have[maxn];void sov() { memset(vis, false, sizeof(false)); memset(size, 0, sizeof(size)); memset(have, 0, sizeof(have)); for(int i = 1; i <= n; ++ i) { if(!dfs[i]) tarjan(i); } memset(in, 0, sizeof(in)); int tol = 0; for(int i = 1; i <= n; ++ i) { for(edge* p = head[i]; p; p = p-> next) { if(belong[p-> t] != belong[i]) { in[belong[p-> t]] ++; } } } int pos = 0; for(int i = 1; i <= num; ++ i) { if(in[i] == 0) tol ++, pos = i; } if(tol == 1) printf("%d\n", size[pos]); else printf("0\n");}int main() { //freopen("test.in", "r", stdin); read(); sov(); return 0;}