1.球员编号从1-n,球迷编号从1-m,有重叠部分,可以将球迷编号整体加n.
2.求最小球员个数等于求球迷的连通分量数,如果某个球迷的度为0表示没有喜欢的球员,此时无解输出-1.
3.变量con表示度为0的球迷的数量,初始值为m,用来判断是否无解,变量ans表示球迷的连通分量数,初始值为m.
4.先将初始状态直接存入map中,key为边,value为边存在的起始时间1.
5.输入修改时,在map中查询是否有这条边,如果有表示此次为删边修改,向线段树插入这条边,插入区间为这条边的存活时间,最后从map中删除这条边.
如果没有这条边就将其加入map中.
6.输入结束后将map中剩余边插入线段树,插入区间即存活时间为该边加入map的时间到所有修改的结束时间Q.
7.查询线段树遍历线段树的所有结点,进入结点时将该结点存储的所有边两端利用并查集合并,如果已经合并在一起了就不用修改,否则需要修改,同时con和ans值也要进行相应的更新,撤销时con和ans也要同时更新.
#include<iostream>
#include<cstdio>
#include<cstring>
#include<vector>
#include<map>
#include<stack>
using namespace std;
const int N=2e5+10;
typedef pair<int,int> pii;
struct node
{int x,y,rx,ry,fx,fy;node(int a,int b,int c,int d,int i,int j):x(a),y(b),rx(c),ry(d),fx(i),fy(j){}
};
map<pii,int>mp;
map<pii,int>::iterator it;
int Q,p[N*2],rk[N*2];
vector<pii>edge[N*4];
stack<node>st;
int deg[N*2];
int con,m,ans;
void add(int now,int l,int r,int x,int y,pii z)
{if(x<=l&&r<=y){edge[now].push_back(z);return;}int mid=(l+r)>>1;if(y<=mid)add(now<<1,l,mid,x,y,z);else if(x>mid)add(now<<1|1,mid+1,r,x,y,z);else{add(now<<1,l,mid,x,y,z);add(now<<1|1,mid+1,r,x,y,z);}
}
int find(int x)
{return p[x]==x?x:find(p[x]);}
void undo()
{node now=st.top();st.pop();p[now.y]=now.y;rk[now.x]=now.rx;deg[now.fy]--;deg[now.fx]--;if(deg[now.fx])ans++;if(!deg[now.fy])con++;
}
void query(int now,int l,int r)
{int tmp=0;for(int i=0;i<edge[now].size();++i){int x=find(edge[now][i].first),y=find(edge[now][i].second);int a=edge[now][i].first,b=edge[now][i].second;if(x==y)continue;tmp++;if(rk[x]<rk[y])swap(x,y);p[y]=x;st.push(node(x,y,rk[x],rk[y],a,b));if(rk[x]==rk[y])rk[x]++;if(deg[a])ans--;if(!deg[b])con--;deg[a]++;deg[b]++;}if(l==r){if(con) printf("-1\n");else printf("%d\n",ans);for(int i=0;i<tmp;++i)undo();return;}int mid=(l+r)>>1;query(now<<1,l,mid);query(now<<1|1,mid+1,r);for(int i=0;i<tmp;++i)undo();
}
int main()
{// freopen("1.txt","r",stdin);int n;cin>>n>>m>>Q;con=m;ans=m;for(int i=1;i<=n+m;++i)p[i]=i;for(int i=1;i<=n;++i){int k;scanf("%d",&k);while(k--){int y;scanf("%d",&y);y+=n;mp[{i,y}]=1;}}for(int i=1;i<=Q;++i){int x,y;scanf("%d%d",&x,&y);x+=n;pii tmp(y,x);it=mp.find(tmp);if(it==mp.end())mp[tmp]=i;else{if(it->second<=i-1)add(1,1,Q,it->second,i-1,tmp);mp.erase(it);}}for(it=mp.begin();it!=mp.end();++it)add(1,1,Q,it->second,Q,it->first);query(1,1,Q);return 0;
}