C++ 算法题：蒜头君的互粉攻略 - 人气指数计算

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' 行，每行输出每个人的人气指数，按编号依次输出即可。

算法

本题可以使用邻接表存储图，然后遍历每个人，计算其粉丝数与关注数之差，即为人气指数。遍历的过程中，可以使用BFS或DFS，也可以直接遍历邻接表。

时间复杂度

使用邻接表存储图，时间复杂度为O(m+n)，其中m为边数，n为节点数。

C++ 代码

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

int main() {
    int n, m;
    cin >> n >> m;
    vector<vector<int>> graph(n); // 邻接表存储图
    for (int i = 0; i < m; ++i) {
        int a, b;
        cin >> a >> b;
        graph[a].push_back(b); // a 关注 b
    }
    vector<int> popularity(n, 0); // 存储每个人的人气指数
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < graph[i].size(); ++j) {
            popularity[graph[i][j]]++; // 统计粉丝数
        }
        popularity[i] -= graph[i].size(); // 减去关注数
    }
    for (int i = 0; i < n; ++i) {
        cout << popularity[i] << endl;
    }
    return 0;
}