題目
每一頭牛的願望就是變成一頭最受歡迎的牛。現在有N頭牛，給你M對整數(A,B)，表示牛A認為牛B受歡迎。這種關系是具有傳遞性的，如果A認為B受歡迎，B認為C受歡迎，那麼牛A也認為牛C受歡迎。你的任務是求出有多少頭牛被所有的牛認為是受歡迎的。
分析
受歡迎的奶牛隻有可能是圖中唯一的出度為零的強連通分量中的所有奶牛，是以若出現兩個以上出度為0的強連通分量則不存在明星奶牛。（tarjan）
tarjan
比kosaraju少了一次深搜。
代碼
#include <cstdio>
#include <cctype>
#include <stack>
using namespace std;
struct node{int x,y,next;}e[50001]; int sum,g;
stack<int>uk; int ans,star[10001],n,m,out[10001],col[10001];
int dfn[10001],low[10001],tot,instack[10001],ls[10001];
int in(){
int ans=0; char c=getchar();
while (!isdigit(c)) c=getchar();
while (isdigit(c)) ans=ans*10+c-48,c=getchar();
return ans;
}
void tarjan(int x){
dfn[x]=low[x]=++tot; uk.push(x); instack[x]=1;//進棧
int t=ls[x];
while (t){
if (!dfn[e[t].y]) //樹枝邊tarjan(e[t].y),low[x]=min(low[x],low[e[t].y]);
else if (instack[e[t].y]) low[x]=min(low[x],dfn[e[t].y]);//傳回邊
t=e[t].next;
}
if (dfn[x]==low[x]){//找到
ans++; int k;
do{//出棧求連通分量
k=uk.top();
star[k]=ans;
col[ans]++;//個數
instack[k]=0;
uk.pop();
}while(k!=x);
}
}
int main(){
n=in(); m=in();
for (int i=1;i<=m;i++)
e[i].x=in(),e[i].y=in(),e[i].next=ls[e[i].x],ls[e[i].x]=i;
for (int i=1;i<=n;i++) if (!dfn[i]) tarjan(i);//沒有通路
for (int i=1;i<=m;i++)
if (star[e[i].x]!=star[e[i].y]) out[star[e[i].x]]++;//不屬于同一個強連通分量
for (int i=1;i<=ans;i++)
if (!out[i]) g=i,sum++;
if (sum>1) puts("0"); else printf("%d",col[g]);
return 0;
}