题解

暴力是很显然的。直接去掉边再跑搜索。

发现操作只有删除，想到逆序操作就变成了增加。

很显然的并查集，在上面多维护一个集合大小就好了。

注意维护一下合并的顺序，无关删除的直接合并，有关的按照输入的逆序处理，最后答案倒过来输出。

别忘了并查集维护的是集合大小，所以用 $n$ 减去集合大小才是答案。

此时还并没有做完。

容易发现，暴力枚举每一个群内的两人关系再合并的时间复杂度过大，所以我们创建 $m$ 个虚点编号为 $n+1$ 到 $n+m$ 表示群聊。

这样我们的复杂度就很低了。

注意，虚点的集合父亲为本身，大小初始化为 $0$。这是因为我们只关心人，而不关心群聊。

时间复杂度：$O(q \log (n+m))$

Code:

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define eb emplace_back
#define pll pair<ll,ll>
#define mkp make_pair
#define fir first
#define sec second
const ll MAXN=2e5+25;
ll n,m,q,s,t;
ll par[MAXN<<1],siz[MAXN<<1];
vector<ll> ans;
vector<pll> a,oper;
set<pll> sets;
inline void init(){
    for(ll i=1;i<=n+m;i++) par[i]=i;
    for(ll i=1;i<=n;i++) siz[i]=1;
    return;
}
inline ll sfind(const ll &x){
    if(par[x]==x) return x;
    return par[x]=sfind(par[x]);
}
inline ll inset(const ll &x,const ll &y){return sfind(x)==sfind(y);}
inline void smerge(const ll &x,const ll &y){
    if(inset(x,y)) return;
    siz[sfind(y)]+=siz[sfind(x)];
    par[sfind(x)]=sfind(y);
    return;
}
int main(){
    cin>>n>>m>>q;
    init();
    for(ll i=1;i<=m;i++){
        cin>>s;
        for(ll j=1;j<=s;j++){
            cin>>t;
            a.eb(t,i+n);
        }
    }
    for(ll i=1;i<=q;i++){
        cin>>s>>t;
        oper.eb(s,t+n);
        sets.insert(mkp(s,t+n));
    }
    for(auto &i:a){
        if(sets.count(i)) continue;
        smerge(i.fir,i.sec);
    }
    reverse(oper.begin(),oper.end());
    for(auto &i:oper){
        ans.eb(siz[sfind(1)]);
        smerge(i.fir,i.sec);
    }
    reverse(ans.begin(),ans.end());
    for(auto &i:ans) cout<<n-i<<'\n';
    return 0;
}