BZOJ1051 [HAOI2006]受欢迎的牛 Tarjan 强连通缩点

欢迎访问~原文出处——博客园-zhouzhendong

去博客园看该题解

---

题目传送门 - BZOJ1051

---

题意概括

　　有n只牛，有m个羡慕关系。

　　羡慕关系具有传递性。

　　如果A羡慕B，B羡慕C，那么我们认为A也羡慕C。

　　问有多少牛被所有其他牛羡慕。

---

题解

　　这次做这题我已经是第三遍了。

　　USACO经典老题啊！（奶牛）

　　POJ上面也有，叫popular cow。

　　做法：

　　先Tarjan强连通缩个点。

　　然后，统计下入度。

　　统计入度为0的点数。如果点数大于1，那么答案明显是0。

　　如果点数是1，那么答案就是唯一的入度为0的点在缩点前点的个数。

---

代码

#include <cstring>

#include <algorithm>

#include <cstdio>

#include <cstdlib>

#include <cmath>

using namespace std;

const int N=+,M=+;

struct Gragh{

    int cnt,x[M],y[M],nxt[M],fst[N];

    void set(){

        cnt=;

        memset(fst,,sizeof fst);

    }

    void add(int a,int b){

        x[++cnt]=a,y[cnt]=b;

        nxt[cnt]=fst[a],fst[a]=cnt;

    }

}g;

int n,m;

int dfn[N],low[N],st[N],time,ans,top,bh[N],cnt[N];

bool inst[N],vis[N];

void Tarjan_Prepare(){

    time=ans=top=;

    memset(bh,,sizeof bh);

    memset(st,,sizeof st);

    memset(dfn,,sizeof dfn);

    memset(low,,sizeof low);

    memset(vis,,sizeof vis);

    memset(inst,,sizeof inst);

}

void Tarjan(int x){

    dfn[x]=low[x]=++time;

    vis[x]=inst[x]=;

    st[++top]=x;

    for (int i=g.fst[x];i;i=g.nxt[i])

        if (!vis[g.y[i]]){

            Tarjan(g.y[i]);

            low[x]=min(low[x],low[g.y[i]]);

        }

        else if (inst[g.y[i]])

            low[x]=min(low[x],low[g.y[i]]);

    if (low[x]==dfn[x]){

        ans++;

        bh[st[top]]=ans;

        inst[st[top]]=;

        while (st[top--]!=x){

            bh[st[top]]=ans;

            inst[st[top]]=;

        }

    }

}

int main(){

    g.set();

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

    for (int i=,a,b;i<=m;i++){

        scanf("%d%d",&a,&b);

        g.add(a,b);

    }

    Tarjan_Prepare();

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

        if (!vis[i])

            Tarjan(i);

    memset(cnt,,sizeof cnt);

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

        if (bh[g.x[i]]!=bh[g.y[i]])

            cnt[bh[g.x[i]]]++;

    int which=-;

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

        if (cnt[i]==){

            if (which!=-){

                printf("");

                return ;

            }

            which=i;

        }

    int Ans=;

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

        if (bh[i]==which)

            Ans++;

    printf("%d",Ans);

    return ;

}