每个球员有一些粉丝，一个粉丝会去看某个球员比赛的条件是
他喜欢这个球员
和他喜欢同一个球员的人喜欢这个球员。
球员与粉丝的关系可以动态改变，问每一次改变之后，最少请多少球员来比赛才可以使得所有粉丝来看比赛。
改变就是对于 b a 两个数，b 是粉丝编号， a 是球员编号，如果 b 是 a 的粉丝，那么现在b 就不是a 的粉丝了，反之 b 变成了 a 的粉丝。
相当于线段树分治，对于每个询问，丢到线段树的每个叶子节点中，然后记录每个关系持续的区间。使用线段树区间覆盖就可以了。
cnt 代表 联通块的个数， cnta 代表单个球员的个数， cntb 代表单个粉丝的个数，
如果 cntb 不是0， 输出 -1， 否则 输出 cnt - cnta
联通块用 并查集来表示， 每次线段树下推的时候要记录一下当前并查集的状态，返回的时候要记得把数据还原。
这个时候的 并查集不能用路径压缩了，而且并查集合并的时候要启发式合并，就是小的集合连接到大的集合上。
#include<bits/stdc++.h> using namespace std; const int N = 4e5+100; typedef pair<int,int>P; struct recv{ int a,asz,b,bsz; int cnt,cnta,cntb; }; struct node{ int l,r; // left and right vector<P>e; vector<recv> rec; }tr[N<<2]; int n,m,q,f[N<<1],cnt,cnta,cntb,ans[N<<1],sz[N<<1]; map<int,int>mp[N]; int find(int k){ if (f[k] == k) return k; return find(f[k]); } void build(int now, int l, int r){ tr[now].l = l; tr[now].r = r; tr[now].e.clear(); tr[now].rec.clear(); if (l == r) return; int mid = (l + r) >> 1; build(now << 1, l, mid); build(now << 1 | 1, mid+1, r); } void update(int now, int l, int r, P p){ if(l <= tr[now].l && r >= tr[now].r) { tr[now].e.push_back(p); return; } int mid = (tr[now].l + tr[now].r) >> 1; if (l <= mid) update(now << 1, l, r, p); if (r >= mid + 1) update(now << 1 | 1,l, r, p); } void solve(int now){ int a,b,len = 0; recv tmp; for (auto it: tr[now].e){ a = find(it.first); b = find(it.second); if (a == b) continue; tmp.cnt = cnt; tmp.cnta = cnta; tmp.cntb = cntb; cnt--; if (sz[a] == 1) cnta--; if (sz[b] == 1) cntb--; if (sz[a] < sz[b]) swap(a,b); tmp.a = a; tmp.b = b; tmp.asz = sz[a]; tmp.bsz = sz[b]; f[b] = a; sz[a] += sz[b]; tr[now].rec.push_back(tmp); len++; } if (tr[now].l == tr[now].r){ if (cntb != 0){ ans[tr[now].l] = -1; } else { ans[tr[now].l] = cnt - cnta; } } else { solve(now << 1); solve(now << 1 | 1); } for (int i = len-1; i >= 0; --i){ tmp = tr[now].rec[i]; cnt = tmp.cnt; cnta = tmp.cnta; cntb = tmp.cntb; f[tmp.a] = tmp.a; f[tmp.b] = tmp.b; sz[tmp.a] = tmp.asz; sz[tmp.b] = tmp.bsz; } } void prework(){ int a,b,k; // a is player b is fan scanf("%d%d%d",&n,&m,&q); build(1,1,q+1); for (int i = 1; i <= n; ++i){ scanf("%d",&k); for (int j = 1; j <= k; ++j){ scanf("%d",&b); mp[i][b] = 1; } } for (int i = 2; i <= q + 1; ++i){ scanf("%d%d",&b,&a); if (mp[a][b] == 0){ mp[a][b] = i; } else { update(1, mp[a][b], i-1,P{a,b+n}); mp[a][b] = 0; } } for (int i = 1; i <= n; ++i){ for (auto it: mp[i]){ if (it.second){ update(1, it.second, q+1, P{i, it.first+n}); } } } cnt = n+m; cnta = n; cntb = m; for (int i = 0; i <= cnt; ++i){ f[i] = i; sz[i] = 1; } } int main(){ prework(); solve(1); for (int i = 2; i <= q+1; ++i) printf("%d\n",ans[i]); return 0; }