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' 行，每行输出每个人的人气指数，按编号依次输出即可。### 算法1并查集对于每个人，维护他的粉丝数和关注数。对于每一条关注，将被关注者的粉丝数加一，将关注者的关注数加一。最后遍历每个人，计算他的人气指数并输出即可。时间复杂度并查集的时间复杂度为 $O(m/alpha(n))$，其中 $/alpha(n)$ 为阿克曼函数的反函数，接近于常数，因此时间复杂度为 $O(m)$。C++ 代码c++#include #include using namespace std;int main() { int n, m; cin >> n >> m; // 存储每个人的粉丝数和关注数 vector fans(n, 0); vector follows(n, 0); // 处理关注关系 for (int i = 0; i < m; ++i) { int a, b; cin >> a >> b; fans[b]++; follows[a]++; } // 计算并输出每个人的人气指数 for (int i = 0; i < n; ++i) { cout << fans[i] - follows[i] << endl; } return 0;}### 算法2拓扑排序对于每个人，维护他的入度和出度。对于每一条关注，将被关注者的入度加一，将关注者的出度加一。然后进行拓扑排序，每次选择入度为零的点并更新其后继节点的入度，直到所有节点都被访问过。最后遍历每个人，计算他的人气指数并输出即可。时间复杂度拓扑排序的时间复杂度为 $O(m+n)$。C++ 代码c++#include #include #include using namespace std;int main() { int n, m; cin >> n >> m; // 存储每个人的入度和出度 vector inDegree(n, 0); vector outDegree(n, 0); // 存储每个人的邻接表 vector<vector> adjList(n); // 处理关注关系 for (int i = 0; i < m; ++i) { int a, b; cin >> a >> b; inDegree[b]++; outDegree[a]++; adjList[a].push_back(b); } // 拓扑排序 queue q; 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 : adjList[u]) { if (--inDegree[v] == 0) { q.push(v); } } } // 计算并输出每个人的人气指数 for (int i = 0; i < n; ++i) { cout << inDegree[i] - outDegree[i] << endl; } return 0;