洛谷 P2341 [HAOI2006]受欢迎的牛 解题报告

P2341 [HAOI2006]受欢迎的牛

题目描述

每头奶牛都梦想成为牛棚里的明星。被所有奶牛喜欢的奶牛就是一头明星奶牛。所有奶

牛都是自恋狂，每头奶牛总是喜欢自己的。奶牛之间的“喜欢”是可以传递的——如果A喜

欢B，B喜欢C，那么A也喜欢C。牛栏里共有N 头奶牛，给定一些奶牛之间的爱慕关系，请你

算出有多少头奶牛可以当明星。

输入输出格式

输入格式：

 第一行：两个用空格分开的整数：N和M

 第二行到第M + 1行：每行两个用空格分开的整数：A和B，表示A喜欢B

输出格式：

 第一行：单独一个整数，表示明星奶牛的数量

说明

【数据范围】

10%的数据N<=20, M<=50

30%的数据N<=1000,M<=20000

70%的数据N<=5000,M<=50000

100%的数据N<=10000,M<=50000

---

考虑到可能存在的环（简单环和非简单环），我们先用tarjan缩点。

对于一个连通图，若某点的出度为0，则图中所有点都可以遍历到它

做完了...

---

code：

#include <cstdio>

#include <queue>

using namespace std;

const int N=10010;

const int M=50010;

struct Edge

{

    int to,next;

}edge[M],edge1[M];

int head[N],cnt=0,head1[N],cnt1=0,n1=0;

void add(int u,int v)

{

    edge[++cnt].next=head[u];edge[cnt].to=v;head[u]=cnt;

}

void add1(int u,int v)

{

    edge1[++cnt1].next=head1[u];edge1[cnt1].to=v;head1[u]=cnt1;

}

int out[N],n,m,dp[N],siz[N],ha[N],low[N],dfn[N],is[N],time=0,s[N],tot=0;

void push(int x){s[++tot]=x;}

void pop(){tot--;}

queue <int > q;

void tarjan(int now)

{

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

    is[now]=1;

    push(now);

    for(int i=head[now];i;i=edge[i].next)

    {

        int v=edge[i].to;

        if(!dfn[v])

        {

            tarjan(v);

            low[now]=min(low[v],low[now]);

        }

        else if(is[v])

            low[now]=min(low[now],dfn[v]);

    }

    if(low[now]==dfn[now])

    {

        int k;

        n1++;

        do

        {

            k=s[tot];

            ha[k]=n1;

            siz[n1]++;

            is[k]=0;

            pop();

        }while(k!=now);

    }

}

int main()

{

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

    int u,v;

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

    {

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

        add(u,v);

    }

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

        if(!dfn[i])

            tarjan(i);

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

        for(int j=head[i];j;j=edge[j].next)

        {

            int v0=edge[j].to;

            if(ha[v0]!=ha[i])

            {

                add1(ha[i],ha[v0]);

                out[ha[i]]++;

            }

        }

    int cntt=0,loc;

    for(int i=1;i<=n1;i++)

    {

        if(!out[i]) loc=i,cntt++;

        if(cntt==2) break;

    }

    if(cntt==2) printf("0\n");

    else printf("%d\n",siz[loc]);

    return 0;

}

---

2018.6.9