微博转发问题题解

题目概述

给定一个有向图，表示用户之间的“关注”关系。若 A 关注 B（即存在有向边 A → B），则 A 是 B 的粉丝。当编号为 ID 的用户（小末）发布微博时，所有能直接或间接关注到小末的用户都会转发该微博。求转发的总人数（不包含小末自己）。

问题分析

关键转化

• 原问题：求有多少个节点 X，在原图中存在路径 X → … → ID。
• 等价问题：在反向图中，从 ID 出发能到达多少个节点（不含 ID 自身）。

为什么用反向图？
在原图中对每个节点判断是否能到达 ID，需要对每个点做搜索，复杂度极高。而将所有边反向后，“X 能到达 ID” 等价于 “在反向图中 ID 能到达 X”，只需从 ID 开始做一次 BFS/DFS 即可求解。

建图规则

输入	含义	反向图操作
A B	A 关注 B（A→B）	rev[B].push_back(A)

示例验证

以样例 1 为例，ID=1。构建反向图后从节点 1 开始 BFS，可访问到的新节点集合为 {2, 3, 4, 5, 6}，共 5 个，因此输出 5 ✅。

算法设计

1. 读取测试数据组数 T。
2. 对每组数据：
   • 读取 N（关系数/边数）和 ID（小末编号）。
   • 构建反向邻接表 revGraph。
   • 从 ID 开始 BFS，统计新访问的节点数 count。
3. 按格式输出 Case #x: count。

复杂度分析

指标	复杂度	说明
时间	O(N + V)	V 为实际出现的节点数，每条边和每个节点最多被访问一次
空间	O(N + V)	存储反向邻接表和访问标记数组

N ≤ 10⁵，该复杂度完全可接受。

C++ 代码实现

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

const int MAXN = 100005;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int T;
    cin >> T;
    for (int caseIdx = 1; caseIdx <= T; ++caseIdx) {
        int N, ID;
        cin >> N >> ID;

        vector<vector<int>> revGraph(MAXN);
        for (int i = 0; i < N; ++i) {
            int A, B;
            cin >> A >> B;
            // A 关注 B => 反向图中建边 B -> A
            revGraph[B].push_back(A);
        }

        vector<bool> visited(MAXN, false);
        queue<int> q;
        int count = 0;

        visited[ID] = true;
        q.push(ID);

        while (!q.empty()) {
            int u = q.front();
            q.pop();
            for (int v : revGraph[u]) {
                if (!visited[v]) {
                    visited[v] = true;
                    count++;
                    q.push(v);
                }
            }
        }

        cout << "Case #" << caseIdx << ": " << count << '\n';
    }
    return 0;
}