题解 | #小A最多会新认识的多少人# 并查集

经典的并查集求无向图连通分量的题目

每读入一组数据，都将其合并进之前的图中

最后统计有几个人与给定的ai处于同一图中即可

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

// 递归查找祖先
int Find(vector<int>& parent, int index) {
    if (parent[index] != index) {
        parent[index] = Find(parent, parent[index]);
    }
    return parent[index];
}

// 合并
void Union(vector<int>& parent, int index1, int index2) {
    int p1 = Find(parent, index1);
    int p2 = Find(parent, index2);
    parent[p1] = p2; // 将p1的祖先设置为p2
}

int main() {
    int n, ai, m;
    cin >> n >> ai >> m;
    
    // 并查集 初始化
    vector<int> parent(n, 0);
    for (int i = 0; i < n; i++) {
        parent[i] = i;
    }

    int alknown = 0; // ai事先认识的数量
    int a, b;
    for (int i = 0; i < m; i++) {
        scanf("%d,%d", &a, &b);
        if (a == ai || b == ai) {
            alknown++;
        }
        Union(parent, a, b);
    }
    
    int ans = 0;
    for (int i = 0; i < n; i++) {
        // 如果i和ai处于同一个连通分量中
        if (Find(parent, i) == Find(parent, ai)) {
            ans++;
        }
    }
    // 注意减去ai事先认识的人数量，再减去ai自己
    cout << ans - alknown - 1 << endl;
    return 0;
}

时间复杂度：

1、初始化并查集，耗时 O(n) ，其中 n 是总人数

2、遍历 m 条边并进行合并操作的时间复杂度为 O(m * α(n))，其中 α(n) 是 Ackermann 函数的反函数，可以看作是一个非常小的常数

3、遍历所有人并统计与 ai 在同一个连通分量中的人数的时间复杂度为 O(n)

综上，时间复杂度为 O(n + m * α(n))

空间复杂度：O(n) ，用于存储 parent 数组