为了方便你创建 OJ（Online Judge）测试数据，我编写了此数据生成器。它包含了并查集 (DSU) 正解逻辑（用于生成 .out）以及针对性数据构造逻辑（用于生成 .in）。

数据生成策略

1. Case 1-3：完全对应题目给出的 3 个示例（边界与基本逻辑）。
2. Case 4 (孤立点)：$N=100$，所有点均不连通，测试索引最小原则。
3. Case 5 (全连通)：$N=100$，团（Clique）结构，测试多源感染块的贡献为 0。
4. Case 6 (链状图)：$N=300$，测试长距离连通性。
5. Case 7 (多源块竞争)：两个大小不同的块，各有 1 个源，测试“拯救最大块”逻辑。
6. Case 8 (星形图)：中心节点是源，测试关键节点移除后的效果。
7. Case 9 (最大规模随机)：$N=300$，稀疏图（$p=0.02$），模拟真实网络。
8. Case 10 (平局判定极限)：多个相同大小的连通块，每个块内仅一个源，测试 initial 排序后的索引最小输出。

数据生成器代码 (C++14)

#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <string>
#include <random>
#include <ctime>
#include <algorithm>
#include <numeric>

using namespace std;

// --- DSU 正解，用于生成 .out 文件 ---
struct DSU {
    vector<int> fa, sz;
    DSU(int n) {
        fa.resize(n);
        iota(fa.begin(), fa.end(), 0);
        sz.assign(n, 1);
    }
    int find(int x) {
        while (x != fa[x]) {
            fa[x] = fa[fa[x]]; // 路径压缩（迭代版，防爆栈）
            x = fa[x];
        }
        return x;
    }
    void unite(int x, int y) {
        int rootX = find(x), rootY = find(y);
        if (rootX != rootY) {
            fa[rootX] = rootY;
            sz[rootY] += sz[rootX];
        }
    }
};

int solve_std(int n, const vector<vector<int>>& graph, vector<int> initial) {
    DSU dsu(n);
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            if (graph[i][j]) dsu.unite(i, j);
        }
    }

    vector<int> malware_cnt(n, 0);
    for (int u : initial) malware_cnt[dsu.find(u)]++;

    sort(initial.begin(), initial.end());
    int max_saved = -1;
    int ans = initial[0];

    for (int u : initial) {
        int root = dsu.find(u);
        if (malware_cnt[root] == 1) {
            int saved = dsu.sz[root];
            if (saved > max_saved) {
                max_saved = saved;
                ans = u;
            }
        }
    }
    return ans;
}

// --- 通用数据写入 ---
// 格式说明：n, 矩阵, k, initial集合
void write_case(int id, int n, const vector<vector<int>>& graph, const vector<int>& initial) {
    string in_name = to_string(id) + ".in";
    string out_name = to_string(id) + ".out";

    ofstream fout(in_name);
    fout << n << "\n";
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            fout << graph[i][j] << (j == n - 1 ? "" : " ");
        }
        fout << "\n";
    }
    // NOI 风格：先输出集合大小 k，再输出集合内容
    fout << initial.size() << "\n";
    for (int i = 0; i < initial.size(); i++) {
        fout << initial[i] << (i == (int)initial.size() - 1 ? "" : " ");
    }
    fout << endl;
    fout.close();

    ofstream fans(out_name);
    fans << solve_std(n, graph, initial) << endl;
    fans.close();
    cout << "Case " << id << " [N=" << n << "] generated." << endl;
}

int main() {
    mt19937 rng(time(0));

    // Case 1, 2, 3: 原始样例
    write_case(1, 3, {{1,1,0},{1,1,0},{0,0,1}}, {0, 1});
    write_case(2, 3, {{1,0,0},{0,1,0},{0,0,1}}, {0, 2});
    write_case(3, 3, {{1,1,1},{1,1,1},{1,1,1}}, {1, 2});

    // Case 4: 孤立点
    {
        int n = 100;
        vector<vector<int>> g(n, vector<int>(n, 0));
        for(int i=0; i<n; i++) g[i][i] = 1;
        write_case(4, n, g, {50, 20, 80});
    }

    // Case 5: 全连通 (Clique)
    {
        int n = 100;
        vector<vector<int>> g(n, vector<int>(n, 1));
        write_case(5, n, g, {10, 20, 30});
    }

    // Case 6: 链状图 (Chain)
    {
        int n = 300;
        vector<vector<int>> g(n, vector<int>(n, 0));
        for(int i=0; i<n; i++) g[i][i]=1;
        for(int i=0; i<n-1; i++) g[i][i+1] = g[i+1][i] = 1;
        write_case(6, n, g, {150});
    }

    // Case 7: 两个大小不同的块
    {
        int n = 300;
        vector<vector<int>> g(n, vector<int>(n, 0));
        for(int i=0; i<n; i++) g[i][i]=1;
        // 块1: 0-99 (size 100), 块2: 100-299 (size 200)
        for(int i=0; i<99; i++) g[i][i+1] = g[i+1][i] = 1;
        for(int i=100; i<299; i++) g[i][i+1] = g[i+1][i] = 1;
        write_case(7, n, g, {5, 150}); // 应该救 150
    }

    // Case 8: 星形图，中心是源
    {
        int n = 300;
        vector<vector<int>> g(n, vector<int>(n, 0));
        for(int i=0; i<n; i++) g[i][i]=1;
        for(int i=1; i<n; i++) g[0][i] = g[i][0] = 1;
        write_case(8, n, g, {0, 5, 10}); // 多源块，选最小索引
    }

    // Case 9: 随机稀疏图 (区分 N^2 和 N^3)
    {
        int n = 300;
        vector<vector<int>> g(n, vector<int>(n, 0));
        for(int i=0; i<n; i++) {
            g[i][i] = 1;
            for(int j=i+1; j<n; j++) 
                if(rng()%100 < 2) g[i][j] = g[j][i] = 1;
        }
        write_case(9, n, g, {1, 10, 100, 200});
    }

    // Case 10: 平局判定 (相同大小块)
    {
        int n = 300;
        vector<vector<int>> g(n, vector<int>(n, 0));
        for(int i=0; i<n; i++) g[i][i]=1;
        // 3个大小为50的块，源点分别为 100, 50, 150
        for(int i=50; i<99; i++) g[i][i+1]=g[i+1][i]=1;
        for(int i=100; i<149; i++) g[i][i+1]=g[i+1][i]=1;
        for(int i=150; i<199; i++) g[i][i+1]=g[i+1][i]=1;
        write_case(10, n, g, {100, 50, 150}); // 结果应为 50
    }

    return 0;
}

关键点说明

1. 文件大小控制：
   • 最大规模 $N=300$。邻接矩阵有 $300 \times 300 = 90,000$ 个数字。
   • 每个数字加空格约 2 字节，单个 .in 文件约 $180$ KB。
   • 10 个测试点总大小约 $1.8$ MB，完美符合 2MB 的限制。
2. 安全性优化：
   • 并查集 find 使用了迭代写法（非递归），彻底杜绝了在深链图中由于递归层数过深导致的 Stack Overflow 风险。
   • 使用 std::vector 动态分配矩阵，避免在栈上分配大数组。
3. NOI 格式处理：
   • 在输入 initial 集合前，我加入了一个整数 k 代表集合大小。这是 NOI 竞赛的常用做法，方便选手使用 for(int i=0; i<k; i++) cin >> initial[i] 读入，避免因处理行末回车或 EOF 导致的读取错误。
4. 无解处理：
   • 所有生成的 initial 均保证存在于 $0 \dots n-1$ 范围内。
   • 逻辑中考虑了“无法拯救任何块（所有源都在多源块）”的情况，自动返回 initial 中索引最小的节点。

在 NOI 竞赛中，图论题目往往要求选手不仅能写出暴力搜索，还能通过观察图的性质（如连通性）将复杂度降低。本题的本质是研究连通分量与感染源的关系。

版本一：暴力模拟 (Simulation + BFS/DFS)

思路： 既然题目要求只移除一个节点，我们可以枚举 initial 数组中的每一个节点 $u$，假设移除它，然后计算剩下的感染节点会扩散到多少个节点。 这种方法最直观，在 $N=300$ 的数据范围内完全可以跑通。

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <cstring>

using namespace std;

int n;
int graph[305][305];
bool vis[305];

// BFS 计算如果 infected_sources 扩散，最终会有多少点被感染
int count_infected(const vector<int>& infected_sources) {
    if (infected_sources.empty()) return 0;
    
    memset(vis, 0, sizeof(vis));
    queue<int> q;
    
    for (int s : infected_sources) {
        q.push(s);
        vis[s] = true;
    }
    
    int cnt = 0;
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        cnt++;
        
        for (int v = 0; v < n; v++) {
            if (graph[u][v] == 1 && !vis[v]) {
                vis[v] = true;
                q.push(v);
            }
        }
    }
    return cnt;
}

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

    if (!(cin >> n)) return 0;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            cin >> graph[i][j];

    // --- 关键修正：先读入集合大小 k ---
    int k;
    if (!(cin >> k)) return 0; 
    vector<int> initial(k);
    for (int i = 0; i < k; i++) {
        cin >> initial[i];
    }

    // 排序：保证结果相同时返回索引最小的
    sort(initial.begin(), initial.end());

    int min_total_infected = 2e9; // 初始化为一个很大的数
    int ans = initial[0];

    // 枚举移除 initial 中的每一个点
    for (int i = 0; i < k; i++) {
        vector<int> current_sources;
        for (int j = 0; j < k; j++) {
            if (i == j) continue; // 模拟移除 initial[i]
            current_sources.push_back(initial[j]);
        }
        
        int total = count_infected(current_sources);
        
        // 关键逻辑：寻找使总感染数最小的移除点
        // 由于 initial 已排序，相等时保留先发现的（索引小的）
        if (total < min_total_infected) {
            min_total_infected = total;
            ans = initial[i];
        }
    }

    cout << ans << endl;
    return 0;
}

• 时间复杂度：$O(M \times N^2)$，其中 $M$ 是 initial 的大小。每次 BFS 扫描矩阵是 $O(N^2)$。
• 空间复杂度：$O(N^2)$ 存储邻接矩阵。

版本二：连通分量分析 (DSU 优化版 —— 推荐正解)

思路优化： 通过观察发现：

1. 恶意软件会在连通块内传播。
2. 如果一个连通块内有 2 个或更多 初始感染点，移除其中任何一个，该块依然会被剩下的感染点传染。贡献为 0。
3. 如果一个连通块内 恰好只有 1 个 初始感染点，移除它，这个块就“得救”了。贡献为该连通块的大小。

算法步骤：

1. 使用并查集 (DSU) 将所有连通的点合并成块。
2. 统计每个块的大小。
3. 统计每个块内包含 initial 中节点的个数。
4. 遍历 initial，寻找“独占”某个块且该块最大的节点。

#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>

using namespace std;

// 使用全局数组，方便在 NOI 环境下管理大内存
int n;
int graph_edge; 
int fa[305], sz[305], malware_cnt[305];

// 迭代版 find，防止在极端链状图中爆栈
int find(int x) {
    int root = x;
    while (fa[root] != root) {
        root = fa[root];
    }
    // 路径压缩
    while (fa[x] != root) {
        int next = fa[x];
        fa[x] = root;
        x = next;
    }
    return root;
}

void unite(int x, int y) {
    int rootX = find(x);
    int rootY = find(y);
    if (rootX != rootY) {
        // 按大小合并或简单合并均可，这里采用简单合并
        fa[rootX] = rootY;
        sz[rootY] += sz[rootX];
    }
}

int main() {
    // 提高 IO 效率
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    if (!(cin >> n)) return 0;

    // 初始化并查集
    for (int i = 0; i < n; i++) {
        fa[i] = i;
        sz[i] = 1;
    }

    // 读入邻接矩阵
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cin >> graph_edge;
            if (graph_edge == 1 && i < j) { // 只需要合并一次
                unite(i, j);
            }
        }
    }

    // --- 关键修正：先读入 initial 数组的大小 k ---
    int k;
    if (!(cin >> k)) return 0;
    vector<int> initial(k);
    for (int i = 0; i < k; i++) {
        cin >> initial[i];
    }

    // 1. 排序：这是处理“索引最小”原则的最简方法
    sort(initial.begin(), initial.end());

    // 2. 统计每个连通块里的初始感染源数量
    for (int u : initial) {
        malware_cnt[find(u)]++;
    }

    int max_saved = -1;
    int ans = initial[0]; // 默认返回排序后的第一个（索引最小）

    // 3. 寻找最优节点
    for (int u : initial) {
        int root = find(u);
        // 只有当该块只有一个传染源时，移除该源才能救下整个块
        if (malware_cnt[root] == 1) {
            int current_saved = sz[root];
            // 注意：这里必须是 > 而不是 >=
            // 这样当 saved 相等时，ans 会保持为第一个发现的（也就是索引最小的）
            if (current_saved > max_saved) {
                max_saved = current_saved;
                ans = u;
            }
        }
    }

    cout << ans << endl;

    return 0;
}

时间复杂度分析思考过程

1. 并查集构建：
   • 遍历 $N \times N$ 邻接矩阵进行 unite。
   • 时间复杂度：$O(N^2 \alpha(N))$，$\alpha$ 是阿克曼函数的反函数，接近常数。
2. 统计阶段：
   • 排序 initial 数组：$O(M \log M)$，其中 $M \le N$。
   • 统计块内感染点：$O(M)$。
   • 寻找最优解：$O(M)$。
3. 结论：
   • 最终复杂度：$O(N^2)$。相比版本一的 $O(N^3)$，这在 $N=1000$ 或更大规模下优势明显。

空间复杂度优化建议

• 空间分析：当前使用 $O(N^2)$ 存储邻接矩阵。在 NOI 竞赛中，如果 $N=10^5$，邻接矩阵会爆炸。
• 优化方案：改用邻接表（vector<int> adj[N]）存储边，并直接利用并查集或 DFS 进行分块。对于此题 $N=300$，邻接矩阵依然是最稳妥简单的写法。

读题关键词与易错点

1. “整个连通分量”：看到它，直接排除掉复杂的点双、边双连通分量，只需要最基本的并查集或 BFS/DFS 划分连通块。
2. “移除恰好一个”：这意味着不需要考虑多个点的组合情况，大大降低了搜索难度。
3. “如果仍然与被感染的节点连接，它最终仍会被感染”：
   • 这是本题最核心的逻辑陷阱。
   • 它意味着：如果一个块里本来就有 2 个病毒源 A 和 B，你移走了 A，病毒源 B 还是会通过网络把 A 以及全块重新感染。
   • 因此，只有当你是块内唯一的病毒源时，移除你才有意义。
4. 排序：在处理“返回索引最小”的要求时，最稳健的做法是一开始就给集合排序，这样在后续 > 比较中，第一个被记录的最优值天然就是索引最小的。