#10091. 「一本通 3.5 例 1」受欢迎的牛（强联通+度数结论）

libreoj10091:
题解：
首先简化一下，若欢迎关系图是一个DAG(有向无环图)，则只要统计每个点的出度，出度为0的点即为受所有牛欢迎的点且只有唯一一个，因为若存在两个以上出度为0的点，它们之间不可能互相欣赏，满足不了题意。
但实际情况可能存在环，环上的顶点互相之间欣赏。此时，若环外的一头牛欣赏环内某头牛，则它必定欣赏环内所有牛；而若环内某头牛欣赏环外一头牛，则环内所有牛也必定欣赏这头牛。则我们把一个环缩成一个新点，记录这个新点的大小(环的顶点数)，这样最后还是等价为DAG，最后统计一下出度，若只有唯一一个，输出这个点的大小，若超过一个则无解

#include<bits/stdc++.h>
typedef long long LL;
using namespace std;
const int maxn=1e4+10;
int n,m;
int dfn[maxn],low[maxn],cnt;
int bcc[maxn],scc;
vector<int> G[maxn],g[maxn];
stack<int> st;
int ins[maxn];
int sum[maxn];
void init()
{
    memset(dfn,0,sizeof(dfn));
    memset(low,0,sizeof(low));
    memset(bcc,0,sizeof(bcc));
    memset(ins,0,sizeof(ins));
    memset(bcc,0,sizeof(bcc));
    memset(sum,0,sizeof(sum));
    cnt=0;
    scc=0;
    for(int i=0;i<=n;i++){
        G[i].clear();
    }
    while(!st.empty()){
        st.pop();
    }
}
void tarjan(int u)
{
   // printf("ko\n");
    dfn[u]=low[u]=++cnt;
    st.push(u);
    ins[u]=1;
    int len=G[u].size();
    for(int i=0;i<len;i++){
        int to=G[u][i];
        if(!dfn[to]){
            tarjan(to);
            low[u]=min(low[u],low[to]);
        }
        else
        if(ins[to]){
            low[u]=min(low[u],dfn[to]);
        }
    }
    if(dfn[u]==low[u]){
        ++scc;
        int m=0;
        while(1){
            int pre=st.top();
            st.pop();
            ins[pre]=0;
            bcc[pre]=scc;
            m++;
            if(pre==u)break;
        }
        sum[scc]=m;
    }
}
void dfs(int u,int fa,int cap)
{
    if(u!=fa){
        sum[u]+=cap;
    }
    int len=g[u].size();
    for(int i=0;i<g[u].size();i++){
        int to=g[u][i];
        dfs(to,fa,cap);
    }
}
int out[maxn];
int main()
{
    scanf("%d%d",&n,&m);
    init();
    int u,v;
    for(int i=1;i<=m;i++){
        scanf("%d%d",&u,&v);
        G[u].push_back(v);
    }
    for(int i=1;i<=n;i++){
        if(!dfn[i]){
            tarjan(i);
        }
    }

    for(int i=1;i<=n;i++){
        for(int j=0;j<G[i].size();j++){
            int u=i,v=G[i][j];
            if(bcc[u]!=bcc[v]){
                //g[bcc[u]].push_back(bcc[v]);
                out[bcc[u]]++;
            }
        }
    }
    int res=0;
    int ans=0;
    for(int i=1;i<=scc;i++){
        if(out[i]==0){
            res++;
            ans=sum[i];
        }
    }
    if(res==1){
        printf("%d\n",ans);
    }
    else{
        printf("0\n");
    }
    return 0;
}