【强连通分量】Bzoj1051 HAOI2006 受欢迎的牛

Description

每一头牛的愿望就是变成一头最受欢迎的牛。现在有N头牛，给你M对整数(A,B)，表示牛A认为牛B受欢迎。 这种关系是具有传递性的，如果A认为B受欢迎，B认为C受欢迎，那么牛A也认为牛C受欢迎。你的任务是求出有多少头牛被所有的牛认为是受欢迎的。

Solution

那么对于x如果可以也就是所有节点都可以到达x，如果无环也就是x要无出度且无出度的点数正好为1(出边连点必到不了x)。

然而这是有环的，那么把强连通分量缩起来就行了。

Code

我这个傻逼现在才会求强连通分量。

而且还只会Kosaraju，现在还没写过Trajan。

#include<cstdio>

const int maxn=1e5+;

int q[maxn],block[maxn],clock,cnt;

int head[maxn],e[maxn],nxt[maxn],k;

int _head[maxn],_e[maxn],_nxt[maxn];

int adde(int u,int v){

    e[++k]=v;

    nxt[k]=head[u],head[u]=k;

    _e[k]=u;

    _nxt[k]=_head[v],_head[v]=k;

}

int n,m;

int vis[maxn],r[maxn],s[maxn];

int dfs1(int u){

    vis[u]=;

    for(int i=head[u];i;i=nxt[i]){

        int v=e[i];

        if(!vis[v]) dfs1(v);

    }

    q[++clock]=u;

}

int dfs2(int u){

    block[u]=cnt;

    s[cnt]++;

    for(int i=_head[u];i;i=_nxt[i]){

        int v=_e[i];

        if(!block[v]) dfs2(v);

    }

}

int main(){

    scanf("%d%d",&n,&m);

    int u,v;

    for(int i=;i<=m;i++){

        scanf("%d%d",&u,&v);

        adde(u,v);

    }

    for(int i=;i<=n;i++)

        if(!vis[i]) dfs1(i);

    for(int i=n;i>=;i--)

        if(!block[q[i]]){

            ++cnt;

            dfs2(q[i]);

        }

    for(int i=;i<=k;i++){

        int x=block[_e[i]],y=block[e[i]];

        if(x==y) continue;

        r[x]++;

    }

    int ans=,ansx;

    for(int i=;i<=cnt;i++)

        if(!r[i]) ans++,ansx=i;

    if(ans==) printf("%d\n",s[ansx]);

    else printf("0\n");

    return ;

}