这题是一道标准的强连通分量题,运用缩点的方法来做。 其实我也花了很多时间弄懂这个瓜皮算法

如果只有一个缩点的出度为0,就可以判断该缩点内的所有奶牛均为明星奶牛

如果有两个以上的缩点出度为0,那说明这两个缩点互不喜欢,所以没有奶牛是明星奶牛

最后吐槽一句,图论的题目定级为何这么高233

···cpp

#include<cstdio>
#include<stack>
using namespace std;
struct node{
    int next;
    int from,to;
}edge[50010];//邻接表存储有向边 
int len=0;//len表示邻接表的大小 
int n,m,sum=0;//sum是dfn的大小 
int head[10010],dfn[10010],low[10010],sin[10010],vis[10010];//head与邻接表有关,dfn是搜索的顺序,low是搜索到的点顺序的最小值,sin[x]表示x是否在栈内,vis[x]表示x是否搜索过 
int colsize,scl[10010],col[10010],ind[10010];//colsize是缩点数组的数量,scl是每个缩点的大小,col[x]表示x属于哪个缩点,ind说明col的入度 
stack <int> s;//栈 
int rin(){//标准读入优化 
    int sum=0;
    char ch=getchar();
    while (ch>'9'||ch<'0') ch=getchar();
    while (ch<='9'&&ch>='0'){
        sum=sum*10+ch-'0';
        ch=getchar();
    }
    return sum;
}
int fmin(int a,int b){return a<b?a:b;}//min函数 
void add(int u,int v){//增加有向边 
    edge[++len].from=u;
    edge[len].to=v;
    edge[len].next=head[u];
    head[u]=len;
}
void tarjan(int u){//tarjan算法 
    dfn[u]=low[u]=++sum;
    s.push(u);
    sin[u]=vis[u]=1;
    for (int i=head[u];i!=-1;i=edge[i].next){
        int v=edge[i].to;
        if (vis[v]==0){
            tarjan(v);
            low[u]=fmin(low[u],low[v]);
        }
        else if (sin[v]==1)
            low[u]=fmin(low[u],dfn[v]);
    }
    if (dfn[u]==low[u]){
        scl[col[u]=++colsize]=1; 
        while (s.top()!=u){
            scl[col[s.top()]=colsize]++;
            sin[s.top()]=0;
            s.pop();
        }
        sin[u]=0;
        s.pop();

}//最后处理完scl是该缩点的大小,然后栈内包括u的缩点的点退栈,col存储的是点属于哪一个缩点

    return;
}
void inpt(){//输入处理 
    n=rin();
    m=rin();
    for (int i=1;i<=n;i++) head[i]=-1; 
    for (int i=1;i<=m;i++){
        int a=rin(),b=rin(); 
        add(b,a);//将有向边加入邻接表,但是这里边是反的方便处理出度将出度变为入度 
    }
}
void work(){//主要处理 
    for (int i=1;i<=n;i++)
        if (vis[i]==0) tarjan(i);//如果这个点没有访问过就tarjan 
    for (int i=1;i<=n;i++)
        for (int j=head[i];j!=-1;j=edge[j].next)
            if (col[i]!=col[edge[j].to]) ind[col[edge[j].to]]++;//如果这个缩点有入边就增加该缩点的入度 
}
void outp(){//输出处理 
    int ans=0;
    for (int i=1;i<=colsize;i++){ 
        if (ind[i]==0&&ans==0) ans=scl[i];//如果该缩点入度(出度)等于0并且只有一种这样的情况就代表该缩点里都是明星奶牛 
        else if(ind[i]==0) ans=-1;//否则就没有明星奶牛 
    }
    printf("%d\n",ans==-1?0:ans);
}
int main(){
    inpt();
    work();
    outp();
    return 0;
}
···