官方题解｜公告

并查集
在解决当前问题时，正向处理存在较大难度，往往需要多次断边，才能成功去除某一连通块。既然直接删边操作复杂，不妨尝试采用离线算法来简化计算。

我们可以逆向思考，将删边操作转换为加边操作。从最后一次删边开始倒序处理，这样问题就转化为：给定一个图，逐步向图中添加边，并在每次加边后确定班长能够通知到的学生集合。我们可以通过并查集解决这个问题。

时间复杂度 O(n)

#include<bits/stdc++.h>
using namespace std;
const int limit = 1e9 + 1;

class DSU {
public:
    DSU(int n, int m) : n(n), fa(n + 1), siz(n + 1) {
        iota(fa.begin(), fa.end(), 0);
        for (int i = 1; i <= m; i++)siz[i] = 1;
    }

    int find(int x) {
        if (fa[x] != x)fa[x] = find(fa[x]);
        return fa[x];
    }

    void merge(int x, int y) {
        x = find(x), y = find(y);
        if (x != y) {
            fa[x] = y;
            siz[y] += siz[x];
        }
    }

    bool same(int x, int y) {
        return find(x) == find(y);
    }

    bool ishead(int x) {
        return x == find(x);
    }

    int size(int x) {
        return siz[find(x)];
    }

private:
    int n;
    vector<int> fa;
    vector<int> siz;
};

int main() {
    ios::sync_with_stdio(0), cin.tie(0);
    int n, m, q;
    cin >> n >> m >> q;
    vector<set<int> > edge(n + 1);
    for (int i = 1; i <= m; i++) {
        int k;
        cin >> k;
        for (int j = 1; j <= k; j++) {
            int s;
            cin >> s;
            edge[s].emplace(i);
        }
    }
    vector<pair<int, int> > ask(q);
    for (auto &[i, j]: ask) {
        cin >> i >> j;
        edge[i].erase(j);
    }
    stack<int> ans;
    DSU d(n + m + 1 , n);
    for (int i = 1; i <= n; i++) {
        for (const auto j: edge[i]) d.merge(i, j + n);
    }
    for (int i = q; i; i--) {
        ans.emplace(n - d.size(1));
        auto [u,v] = ask[i - 1];
        d.merge(u, v + n);
    }
    while (!ans.empty()) {
        auto t = ans.top();
        ans.pop();
        cout << t << endl;
    }
}