题解：受欢迎的牛问题

一、题目背景

有 (N) 头牛，编号从 (1) 到 (N) ，给定 (M) 对整数 ((A,B)) ，表示牛 (A) 认为牛 (B) 受欢迎，且这种关系具有传递性。需要找出被除自己之外的所有牛都认为是受欢迎的牛的数量。

二、解题思路

本题可通过Tarjan算法求解强连通分量，然后根据强连通分量的出度情况来确定受欢迎的牛的数量。首先利用Tarjan算法将图中的强连通分量找出，然后统计每个强连通分量的出度，若只有一个强连通分量的出度为 (0) ，则该强连通分量中的牛就是被除自己之外的所有牛认为受欢迎的牛。

具体步骤如下：
1. 定义图的存储结构，包括邻接表相关数组、时间戳数组 dfn[N]（记录节点首次访问的时间戳）、追溯数组 low[N]（记录节点或其子孙能追溯到的最早时间戳）、栈数组 stk[N] 及栈顶指针 top、节点是否在栈中的标记数组 in_stk[N]、节点所属强连通分量编号数组 id[N]、强连通分量数量 scc_cnt、每个强连通分量的大小数组 Size[N] 和每个强连通分量的出度数组 dout[N]。
2. 编写添加边的函数，用于构建邻接表。
3. 实现Tarjan算法函数 tarjan，用于找出图中的强连通分量：
- 更新当前节点的 dfn 和 low 值，并将节点入栈，标记在栈中。
- 遍历当前节点的邻接边，对于未访问的节点，递归调用 tarjan 并更新 low 值；对于已访问且在栈中的节点，更新 low 值。
- 若当前节点的 dfn 和 low 值相等，则表示找到了一个强连通分量，将栈中节点弹出，标记不在栈中，并记录所属强连通分量编号和大小。
4. 在 main 函数中：
- 读取牛的数量 n 和关系对数量 m，初始化邻接表。
- 读取每对关系，构建图的邻接表。
- 对每个未访问的节点调用 tarjan 算法，找出所有强连通分量。
- 遍历图的边，统计每个强连通分量的出度。
- 统计出度为 (0) 的强连通分量的数量和对应强连通分量的大小之和，若出度为 (0) 的强连通分量数量大于 (1) ，则不存在这样的牛，数量为 (0)；否则，该大小之和就是受欢迎的牛的数量。

三、代码逐段分析

（一）头文件和全局变量

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 10010, M = 50010;

int n, m;
int h[N], e[M], ne[M], idx;
int dfn[N], low[N], timestamp;
int stk[N], top;
bool in_stk[N];
int id[N], scc_cnt, Size[N];
int dout[N];

1. 头文件：
   • #include <cstdio>：用于标准输入输出函数，如 scanf 和 printf。
   • #include <cstring>：用于字符串操作和内存初始化函数，如 memset。
   • #include <iostream>：提供C++风格的输入输出流，如 cin 和 cout。
   • #include <algorithm>：包含一些常用的算法函数。
   • using namespace std;：使用标准命名空间，以便直接使用标准库中的函数和类型。
2. 常量定义：
   • const int N = 10010, M = 50010;：定义节点的最大数量（牛的数量）和边的最大数量。
3. 变量定义：
   • int n, m;：分别表示牛的数量和关系对的数量。
   • int h[N], e[M], ne[M], idx;：邻接表相关数组，h[N] 存储每个节点的头指针，e[M] 存储边的终点，ne[M] 存储下一条边的指针，idx 用于边的编号。
   • int dfn[N], low[N], timestamp;：dfn[N] 记录节点首次访问的时间戳，low[N] 记录节点或其子孙能追溯到的最早时间戳，timestamp 是时间戳计数器。
   • int stk[N], top;：stk[N] 是栈数组，top 是栈顶指针。
   • bool in_stk[N];：标记每个节点是否在栈中。
   • int id[N], scc_cnt, Size[N];：id[N] 记录节点所属强连通分量编号，scc_cnt 是强连通分量数量，Size[N] 存储每个强连通分量的大小。
   • int dout[N];：记录每个强连通分量的出度。

（二）添加边函数

void add(int a, int b)
{
    e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
}

该函数用于向邻接表中添加一条边，参数 a 为起点，b 为终点。通过更新邻接表数组，将边的信息存储起来。

（三）Tarjan算法函数

void tarjan(int u)
{
    dfn[u] = low[u] = ++ timestamp;
    stk[ ++ top] = u, in_stk[u] = true;
    for (int i = h[u]; i != -1; i = ne[i])
    {
        int j = e[i];
        if (!dfn[j])
        {
            tarjan(j);
            low[u] = min(low[u], low[j]);
        }
        else if (in_stk[j]) low[u] = min(low[u], dfn[j]);
    }

    if (dfn[u] == low[u])
    {
        ++ scc_cnt;
        int y;
        do {
            y = stk[top -- ];
            in_stk[y] = false;
            id[y] = scc_cnt;
            Size[scc_cnt] ++ ;
        } while (y != u);
    }
}

1. 初始化当前节点的 dfn 和 low 值为当前时间戳，将节点入栈并标记在栈中。
2. 遍历当前节点的邻接边：
   • 若邻接节点未访问，递归调用 tarjan 函数，并更新当前节点的 low 值为当前 low 值和邻接节点 low 值的较小值。
   • 若邻接节点已访问且在栈中，更新当前节点的 low 值为当前 low 值和邻接节点 dfn 值的较小值。
3. 若当前节点的 dfn 和 low 值相等，说明找到了一个强连通分量：
   • 强连通分量数量加 (1)。
   • 从栈中弹出节点，标记不在栈中，记录所属强连通分量编号，增加对应强连通分量的大小。

（四）main 函数

int main()
{
    scanf("%d%d", &n, &m);
    memset(h, -1, sizeof h);
    while (m -- )
    {
        int a, b;
        scanf("%d%d", &a, &b);
        add(a, b);
    }

    for (int i = 1; i <= n; i ++ )
        if (!dfn[i])
            tarjan(i);

    for (int i = 1; i <= n; i ++ )
        for (int j = h[i]; ~j; j = ne[j])
        {
            int k = e[j];
            int a = id[i], b = id[k];
            if (a != b) dout[a] ++ ;
        }

    int zeros = 0, sum = 0;
    for (int i = 1; i <= scc_cnt; i ++ )
        if (!dout[i])
        {
            zeros ++ ;
            sum += Size[i];
            if (zeros > 1)
            {
                sum = 0;
                break;
            }
        }

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

    return 0;
}

1. 读取牛的数量 n 和关系对数量 m，初始化邻接表。
2. 读取每对关系，构建图的邻接表。
3. 对每个未访问的节点调用 tarjan 算法，找出所有强连通分量。
4. 遍历图的边，统计每个强连通分量的出度。
5. 初始化出度为 (0) 的强连通分量数量 zeros 和对应强连通分量大小之和 sum：
   • 遍历每个强连通分量，若出度为 (0)，则数量加 (1)，大小之和增加对应强连通分量的大小。
   • 若出度为 (0) 的强连通分量数量大于 (1) ，则将大小之和设为 (0) 并结束循环。
6. 输出大小之和，即受欢迎的牛的数量。
7. 程序结束。

四、时间复杂度和空间复杂度分析

（一）时间复杂度

1. 建图：读取 (m) 条边构建邻接表，时间复杂度为 (O(m))。
2. Tarjan算法：每个节点最多被访问一次，每条边最多被遍历一次，时间复杂度为 (O(n + m))。
3. 统计出度和结果：遍历 (n) 个节点和 (m) 条边统计出度，时间复杂度为 (O(n + m))；遍历 (scc_cnt) 个强连通分量统计结果，时间复杂度为 (O(scc_cnt))，(scc_cnt\leq n)。
   总体时间复杂度为 (O(n + m))。

（二）空间复杂度

1. 邻接表：存储边的信息，空间复杂度为 (O(m))。
2. 其他数组：时间戳数组 dfn[N]、追溯数组 low[N]、栈数组 stk[N]、节点是否在栈中的标记数组 in_stk[N]、节点所属强连通分量编号数组 id[N]、每个强连通分量的大小数组 Size[N] 和每个强连通分量的出度数组 dout[N]，空间复杂度均为 (O(n))。
   总体空间复杂度为 (O(n + m))。

希望这份题解能帮助你理解这道题的解题思路和代码实现。如果有任何疑问，欢迎随时提问。