C++ 拓扑排序算法实现：蒜头君的互粉游戏

蒜头君和他的同事们最近在玩一个好玩的游戏：互粉攻略。一共有 'N' 个人参加游戏，编号从 '0' 到 'N - 1'，游戏前每个人都会展示自己最靓丽的一面。当游戏开始时，每个人可以选择去关注别人。当 'A' 关注了 'B'，则 'A' 就成了 'B' 的粉丝，但是并不意味着 'B' 同时关注了 'A'。当所有人都选好后，游戏结束，人气指数最高的人成为冠军。

蒜头君制定了奇怪的规定：一个人的人气指数等于他的粉丝数减去关注数，因为蒜头君觉得人气高的人，往往有很多粉丝，并且一般都非常高冷，很少去关注别人。

蒜头君发现一共有 'M' 条关注，粗心的他在统计时出了点小问题，所以可能会出现重复的关注。现在蒜头君想知道每个人的人气指数，聪明的你能帮帮他么？

输入格式

第一行输入两个数 'n' 和 'm'，1 ≤ n ≤ 1000，1 ≤ m ≤ 100000。

接下来输入 'm' 行，每行输入两个数 'a' 和 'b'，表示编号 'a' 的人关注了编号 'b' 的人，0 ≤ a, b ≤ n - 1，a ≠ b。

输出格式

输出 'N' 行，每行输出每个人的人气指数，按编号依次输出即可。

算法

本题可以用拓扑排序解决。

首先建立一个邻接表来存储图，对于每个点，用 inDegree 数组记录其入度，即关注它的人的数量。然后进行拓扑排序，每次找到入度为 0 的点，将其出队，并更新其关注的人的入度，直到队列为空。在出队时，可以同时更新每个点的粉丝数和关注数，最后根据公式计算得到每个点的人气指数。

C++ 代码

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

int main() {
    int n, m;
    cin >> n >> m;

    // 邻接表存储图
    vector<vector<int>> graph(n);
    // 每个点的入度
    vector<int> inDegree(n, 0);
    // 每个点的粉丝数
    vector<int> fans(n, 0);
    // 每个点的关注数
    vector<int> follow(n, 0);

    // 输入关注关系
    for (int i = 0; i < m; i++) {
        int a, b;
        cin >> a >> b;
        graph[a].push_back(b);
        inDegree[b]++;
        follow[a]++;
    }

    // 拓扑排序
    queue<int> q;
    // 初始化队列，将入度为 0 的点入队
    for (int i = 0; i < n; i++) {
        if (inDegree[i] == 0) {
            q.push(i);
        }
    }

    // 拓扑排序过程
    while (!q.empty()) {
        int u = q.front();
        q.pop();

        // 更新关注的人的入度
        for (int v : graph[u]) {
            inDegree[v]--;
            // 入度为 0 的点入队
            if (inDegree[v] == 0) {
                q.push(v);
            }
        }

        // 更新粉丝数
        fans[u] += graph[u].size();
    }

    // 计算人气指数并输出
    for (int i = 0; i < n; i++) {
        int popularity = fans[i] - follow[i];
        cout << popularity << endl;
    }

    return 0;
}