BZOJ 1051 受欢迎的牛（Tarjan缩点）

2022-10-22 12:45:47

1051: [HAOI2006]受欢迎的牛

Time Limit: 10 Sec Memory Limit: 162 MB
Submit: 4573 Solved: 2428
[Submit][Status][Discuss]

Description

　　每一头牛的愿望就是变成一头最受欢迎的牛。现在有N头牛，给你M对整数(A,B)，表示牛A认为牛B受欢迎。这

种关系是具有传递性的，如果A认为B受欢迎，B认为C受欢迎，那么牛A也认为牛C受欢迎。你的任务是求出有多少头

牛被所有的牛认为是受欢迎的。

Input

　　第一行两个数N,M。接下来M行，每行两个数A,B，意思是A认为B是受欢迎的（给出的信息有可能重复，即有可

能出现多个A,B）

Output

　　一个数，即有多少头牛被所有的牛认为是受欢迎的。

Sample Input

3 3
1 2
2 1
2 3

Sample Output

HINT

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

题目链接：BZOJ 1051

做法：Tarjan缩点后，由于缩点后必定是一个DAG或者叫有向无环图，因此应该至少存在一个出度为0的缩点和一个入度为0的缩点，这题就是要统计出度为0的分量个数

若统计的数量有为1个，则说明全在一个连通分量内，即任意两点互相可达，所有牛都是受欢迎的；若大于1，则说明至少一个连通分量中的牛的数量少于n-1即欢迎不能直接或间接地全部集中在至少一头牛身上，就没有牛受欢迎了

代码：

#include <stdio.h>

#include <bits/stdc++.h>

using namespace std;

#define INF 0x3f3f3f3f

#define CLR(arr,val) memset(arr,val,sizeof(arr))

#define LC(x) (x<<1)

#define RC(x) ((x<<1)+1)

#define MID(x,y) ((x+y)>>1)

typedef pair<int,int> pii;

typedef long long LL;

const double PI=acos(-1.0);

const int N=10010;

const int M=50010;

struct edge

{

    int to;

    int pre;

};

edge E[M];

int head[N],tot;

int dfn[N],low[N],st[N],belong[N],ins[N],sc,ts,top,scnum[N];

int out[N];

void init()

{

    CLR(head,-1);

    CLR(low,0);

    CLR(dfn,-1);

    CLR(belong,0);

    CLR(ins,0);

    sc=ts=top=0;

    CLR(scnum,0);

    CLR(out,0);

}

inline void add(int s,int t)

{

    E[tot].to=t;

    E[tot].pre=head[s];

    head[s]=tot++;

}

void Tarjan(int u)

{

    dfn[u]=low[u]=++ts;

    ins[u]=1;

    st[top++]=u;

    int v;

    for (int i=head[u]; ~i; i=E[i].pre)

    {

        v=E[i].to;

        if(dfn[v]==-1)

        {

            Tarjan(v);

            if(low[v]<low[u])

                low[u]=low[v];

        }

        else if(ins[v])

        {

            if(dfn[v]<low[u])

                low[u]=dfn[v];

        }

    }

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

    {

        ++sc;

        do

        {

            v=st[--top];

            ins[v]=0;

            belong[v]=sc;

            ++scnum[belong[v]];

        }while (u!=v);

    }

}

int main(void)

{

    int n,m,a,b,i,j,u,v;

    while (~scanf("%d%d",&n,&m))

    {

        init();

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

        {

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

            add(a,b);

        }

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

            if(dfn[i]==-1)

                Tarjan(i);

        for (u=1; u<=n; ++u)

        {

            for (j=head[u]; ~j; j=E[j].pre)

            {

                v=E[j].to;

                if(belong[v]==belong[u])

                    continue;

                ++out[belong[u]];

            }

        }

        int zero_out=0;

        int scindx=-1;

        for (i=1; i<=sc; ++i)

        {

            if(!out[i])

            {

                ++zero_out;

                scindx=i;

            }

        }

        zero_out>1?puts("0"):printf("%d\n",scnum[scindx]);

    }

    return 0;

}

码农公寓