bzoj1051 [HAOI2006]受欢迎的牛

2022-12-06 07:20:53

1051: [HAOI2006]受欢迎的牛

Time Limit: 10 Sec Memory Limit: 162 MB
Submit: 4773 Solved: 2541
[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

分析：对于这道题，可以很自然地想到强连通分量，为什么呢？因为如果答案只有1头牛，那么这头牛肯定在由自己一个点组成的强连通分量里，如果答案大于1，那么符合要求的牛必然在同一个强连通分量里，而且只有一个强连通分量符合要求，这个可以简单的证明一下：假设符合要求的强连通分量有n个，那么第n个强连通分量必然与第n-1个强连通分量联通，这样就组成了一个强连通分量，由此可类推符合要求的强连通分量只有1个.

根据这个，我们在统计答案的时候如果发现符合要求的强连通分量大于1个，那么就无解.怎么知道这个强连通是否符合要求呢？很简单，出度为0即可，如果出度不为0，那么这个“强连通分量”就是另外一个强连通分量的一部分,至于怎么找出度，dfs建图乱搞一下就好了.

#include <cstdio>

#include <stack>

#include <cstring>

#include <iostream>

#include <algorithm>

using namespace std;

const int maxn = , maxm = ;

int n, m,head[maxn],to[maxm],nextt[maxm],tot,scc[maxn],dfsclock,low[maxn],pre[maxn],num,shuliang[maxn],ans;

int head2[maxn], to2[maxn], nextt2[maxn], tot2;

stack <int> s;

void add(int x, int y)

{

    tot++;

    to[tot] = y;

    nextt[tot] = head[x];

    head[x] = tot;

}

void add2(int x, int y)

{

    tot2++;

    to2[tot2] = y;

    nextt2[tot2] = head2[x];

    head2[x] = tot2;

}

void tarjan(int u)

{

    s.push(u);

    low[u] = pre[u] = ++dfsclock;

    for (int i = head[u];i;i = nextt[i])

    {

        int v = to[i];

        if (!pre[v])

        {

            tarjan(v);

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

        }

        else

            if (!scc[v])

                low[u] = min(low[u], pre[v]);

    }

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

    {

        num++;

        while ()

        {

            int t = s.top();

            s.pop();

            scc[t] = num;

            shuliang[num]++;

            if (t == u)

                break;

        }

    }

}

void lianbian(int u)

{

    for (int i = head[u]; i; i = nextt[i])

    {

        int v = to[i];

        if (scc[u] != scc[v])

            add2(scc[u], scc[v]);

    }

}

int main()

{

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

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

    {

        int a, b;

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

        add(a, b);

    }

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

        if (!scc[i])

            tarjan(i);

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

        lianbian(i);

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

        if (!head2[i])

        {

            if (ans)

            {

                printf("0\n");

                return ;

            }

            ans = shuliang[i];

        }

    printf("%d\n", ans);

    return ;

}

码农公寓