题解：寻找疑似患者（The Suspects）

题目分析

本题要求计算在多个学生团体中，当学生0为疑似患者时，所有可能被感染的学生总数。核心在于：若某团体中存在疑似患者，则该团体所有成员均为疑似患者。因此，问题转化为通过并查集（Union-Find）算法，将同一团体的学生合并到同一个集合中，并统计包含学生0的集合的大小。

方法思路

1. 并查集算法：

   • 初始化：每个学生独立为一个集合，父节点为自身。
   • 合并操作：对于每个团体，将团体中的所有学生合并到同一个集合中（只需将他们的父节点统一）。
   • 查找根节点：通过路径压缩优化查找过程，确保每次查找根节点的时间接近常数。

2. 步骤：

   • 读取学生数n和团体数m。
   • 对每个团体，将其中的学生逐一合并到并查集中。
   • 查找学生0所在集合的根节点，并统计该集合的大小。

解决代码（C++）

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

const int MAXN = 30005; // 学生编号最大为30000，+5确保安全
int parent[MAXN], size[MAXN]; // parent[i]存储i的父节点，size[i]存储集合大小

// 初始化并查集
void init(int n) {
    for (int i = 0; i < n; ++i) {
        parent[i] = i;
        size[i] = 1;
    }
}

// 查找根节点（路径压缩）
int find(int x) {
    if (parent[x] != x) {
        parent[x] = find(parent[x]); // 路径压缩
    }
    return parent[x];
}

// 合并两个集合（按秩合并）
void unite(int x, int y) {
    x = find(x);
    y = find(y);
    if (x == y) return;
    // 将较小的集合合并到较大的集合中
    if (size[x] < size[y]) {
        swap(x, y);
    }
    parent[y] = x;
    size[x] += size[y];
}

int main() {
    int n, m;
    while (cin >> n >> m && n != 0) {
        init(n); // 初始化并查集
        for (int i = 0; i < m; ++i) {
            int k, first;
            cin >> k;
            if (k == 0) continue; // 空团体，跳过
            cin >> first; // 读取第一个学生
            for (int j = 1; j < k; ++j) {
                int student;
                cin >> student;
                unite(first, student); // 合并同一团体的学生
            }
        }
        // 查找学生0所在集合的大小
        int root = find(0);
        cout << size[root] << endl;
    }
    return 0;
}

代码解释

1. 并查集初始化：

   • parent数组存储每个节点的父节点，初始时每个节点的父节点为自身。
   • size数组存储以每个节点为根的集合的大小，初始时每个集合大小为1。

2. 路径压缩：

   • 在查找根节点时，将路径上的所有节点直接指向根节点，减少后续查找的时间复杂度。

3. 按秩合并：

   • 合并两个集合时，将较小的集合合并到较大的集合中，确保树的高度不会过快增长，进一步优化查找效率。

4. 输入处理：

   • 对于每个团体，读取第一个学生作为基准，将后续学生逐一与基准学生合并，确保同一团体的学生属于同一集合。
   • 最后通过查找学生0的根节点，获取其所在集合的大小，即为疑似患者总数。

复杂度分析

• 时间复杂度：
  • 初始化：(O(n))。
  • 合并和查找操作：每个操作的时间复杂度接近(O(\alpha(n)))，其中(\alpha)为阿克曼函数的反函数，可视为常数。总时间复杂度为(O(m \times k + n \times \alpha(n)))，其中(k)为团体平均人数，满足题目约束。
• 空间复杂度：(O(n))，用于存储父节点和集合大小。

该方法高效地解决了动态合并集合和查询集合大小的问题，适用于题目给定的数据范围。