每个强连通分量里奶牛的爱慕关系都是可以互相传递的，也就是说他们互相爱慕。
那么跑一遍缩点，然后拓扑排序再 DP 出能到达每个强连通分量的点数，最后那个能被所有点到达的强连通分量的点数就是答案了。时间复杂度 \(O(N+M)\)
其实还有另外一种线性的做法，这里口胡下
在缩点后，如果有两个或以上的强连通分量的出度为 0，那么这时一定是没有明星奶牛的。
那么，那个唯一出度为 0 的强连通分量的点数就是答案了。
这里只有第一种做法的代码，我太蒻了
#include#include #include #include const int MaxN = 10000 + 5;const int MaxM = 50000 + 5;int N, M, Ans, Index, Scc, Edge, Head, Tail, Top;int Dfn[MaxN], Low[MaxN], Belong[MaxN], FST[MaxN], Cnt[MaxN], Dp[MaxN], Stack[MaxN], Q[MaxN], Indegree[MaxN], A[MaxN];bool InStack[MaxN];struct SccEdge{ int from, to;} SE[MaxM];struct Linker{ int to, nxt; Linker(){} Linker(int u, int v) { to = v; nxt = FST[u]; }} E[MaxM];inline int read(){ register int x = 0; register char ch = getchar(); while(!isdigit(ch)) ch = getchar(); while(isdigit(ch)) { x = x * 10 + ch - '0'; ch = getchar(); } return x;}void AddEdge(int u, int v){ E[++Edge] = Linker(u, v); FST[u] = Edge;}void Tarjan(int x){ Dfn[x] = Low[x] = ++Index; Stack[++Tail] = x; InStack[x] = 1; for(int k = FST[x]; k; k = E[k].nxt) { int to = E[k].to; if(!Dfn[to]) { Tarjan(to); Low[x] = std::min(Low[x], Low[to]); } else if(InStack[to]) Low[x] = std::min(Low[x], Dfn[to]); } if(Dfn[x] == Low[x]) { ++Scc; int t; do { t = Stack[Tail--]; InStack[t] = 0; Belong[t] = Scc; ++Cnt[Scc]; } while(t != x); }}bool comp(SccEdge x, SccEdge y){ return x.from < y.from || (x.from == y.from && x.to < y.to);}void TopSort(){ Head = 1; for(int i = 1; i <= Scc; ++i) if(!Indegree[i]) A[++Top] = Q[++Tail] = i; while(Head <= Tail) { int from = Q[Head++]; for(int k = FST[from]; k; k = E[k].nxt) { int to = E[k].to; if(!(--Indegree[to])) A[++Top] = Q[++Tail] = to; } }}int main(){ N = read(); M = read(); for(int i = 1; i <= M; ++i) { SE[i].from = read(); SE[i].to = read(); AddEdge(SE[i].from, SE[i].to); } for(int i = 1; i <= N; ++i) if(!Dfn[i]) Tarjan(i); for(int i = 1; i <= M; ++i) { SE[i].from = Belong[SE[i].from]; SE[i].to = Belong[SE[i].to]; } std::sort(SE + 1, SE + 1 + M, comp); Edge = 0; memset(FST, 0, sizeof(FST)); for(int i = 1; i <= M; ++i) { if((SE[i].from != SE[i - 1].from || SE[i].to != SE[i - 1].to) && SE[i].from != SE[i].to) { AddEdge(SE[i].from, SE[i].to); ++Indegree[SE[i].to]; } } TopSort(); for(int i = 1; i <= Scc; ++i) { int from = A[i]; Dp[from] += Cnt[from]; if(Dp[from] >= N) Ans += Cnt[from]; for(int k = FST[from]; k; k = E[k].nxt) { int to = E[k].to; Dp[to] += Dp[from]; } } printf("%d\n", Ans); return 0;}