练习

[USACO03FALL / HAOI2006] 受欢迎的牛 G

每头奶牛都梦想成为牛棚里的明星。被所有奶牛喜欢的奶牛就是一头明星奶牛。所有奶牛都是自恋狂，每头奶牛总是喜欢自己的。奶牛之间的“喜欢”是可以传递的——如果 \(A\) 喜欢 \(B\)，\(B\) 喜欢 \(C\)，那么 \(A\) 也喜欢 \(C\)。牛栏里共有 \(N\) 头奶牛，给定一些奶牛之间的爱慕关系，请你算出有多少头奶牛可以当明星。

输入格式

第一行：两个用空格分开的整数：\(N\) 和 \(M\)。

接下来 \(M\) 行：每行两个用空格分开的整数：\(A\) 和 \(B\)，表示 \(A\) 喜欢 \(B\)。

---

缩点后会变成一棵树。找到没有出度的那个点u，u中包含是所有奶牛都是明星。如果有多个点没有出度，则答案为0，即奶牛分成了若干个阵营，相互不连通。

/*////////ACACACACACACAC///////////
       . Coding by Ntsc .
       . Prove Yourself .
/*////////ACACACACACACAC///////////

#include<bits/stdc++.h>
#define ll long long
#define db double
#define rtn return
#define i1n int i=1;i<=n;i++
#define in1 int i=n;i>=1;i--
using namespace std;

const int N=5e5+5;
const int M=1e5;
const int Mod=1e5;
const int INF=1e5;

int dfn[N],low[N],stk[N],tot,top,cnt,scc[N],siz[N],sccw[N],w[N],dis[N],vis[N],n,m,way[N][2],instk[N],s,np,p[N],ans;
vector <int> e[N];
int du[N];
int f[N];


vector<int>e2[N];

void add(int a,int b){
    e[a].push_back(b);
}
void add2(int a,int b){
    e2[a].push_back(b);
    du[a]++;
}

void tarjan(int x){//强连通分量缩点
    //入x时,时间戳追溯值更新,入栈
    dfn[x]=low[x]=++tot;
    stk[++top]=x;instk[x]=1; 

    for(int i=0;i<e[x].size();i++){//枚举x的邻点y 
        int y=e[x][i];
        if(!dfn[y]){//如果y还没有访问过 
            tarjan(y);//向下走 
            low[x]=min(low[x],low[y]);//返回时更新 
        }else if(dfn[y]&&instk[y]){//说明 y被访问过 ->要么y是祖先(在x出通过返祖边访问到了),要么是左子树的点(在x通过横插边访问到了) 
            low[x]=min(low[x],dfn[y]); 
        }
    }
    if(dfn[x]==low[x]){//说明x是这个强连通分量的根 
        int y;++cnt;
        int flag=0;
        do{
            flag++;
            y=stk[top--];instk[y]=0;
            scc[y]=cnt;
            ++siz[cnt];
            sccw[cnt]+=w[y];//记录缩点后强连通分量点的点权
        } while(y!=x); 
    }
}

void dfs(int x){
    if(f[x])return ;
    f[x]=sccw[x];
    int mx=0;
    for(auto v:e2[x]){
        if(!f[v])dfs(v);//搜过就不用再搜，直接调用 
        mx=max(mx,f[v]);
    }
    f[x]+=mx;
}

signed main(){
    cin>>n>>m;
    for(int i=1;i<=m;i++){
        cin>>way[i][0]>>way[i][1];
    }

    for(int i=1;i<=m;i++){
        add(way[i][0],way[i][1]);
    }


    for(int i=1;i<=n;i++)//题目不保证图连续!
        if(!dfn[i]) tarjan(i);

    //建新图 
    for(int i=1;i<=n;i++){
        for(int j=0;j<e[i].size();j++){
            int v=e[i][j];
            if(scc[i]==scc[v])continue;//注意continue
            add2(scc[i],scc[v]);//注意不是scc[j]
        }
    }
    int res=0;
    for(int i=1;i<=cnt;i++){
        if(!du[i])res++,ans=siz[i];
        if(res>1){
            ans=0;break;
        }
    } 

    cout<<ans<<endl;
    return 0;
}