题目大意:有一个无向图,依次击破一些点,求每次击破后的联通块个数
题解:离线解决,把击破变成添加,倒着处理,每次添加节点时把与它相连的边加入图中,用并查集维护,求出答案
C++ Code:
#include<cstdio> using namespace std; const int maxm=200010; const int maxn=400010; int n,m,k,num; int ans[maxn],f[maxn],s[maxn]; bool v[maxn]; int head[maxn],cnt; struct Edge{ int from,to,nxt; }e[maxm<<1]; void add(int a,int b){ e[++cnt]=(Edge){a,b,head[a]}; head[a]=cnt; } int find(int x){return x==f[x]?x:(f[x]=find(f[x]));} int main(){ scanf("%d%d",&n,&m); for (int i=0;i<m;i++){ int a,b; scanf("%d%d",&a,&b); add(a,b); add(b,a); } scanf("%d",&k); for (int i=1;i<=k;i++)scanf("%d",&s[i]),v[s[i]]=1; for (int i=0;i<n;i++)f[i]=i; for (int i=0;i<m;i++){ if ((!(v[e[i<<1|1].from]))&&(!(v[e[i<<1|1].to]))){ int x=find(e[i<<1|1].from),y=find(e[i<<1|1].to); if (x!=y){ num++; f[x]=f[y]; } } } ans[k]=n-k-num; for (int i=k-1;i>=0;i--){ v[s[i+1]]=0; for (int j=head[s[i+1]];j;j=e[j].nxt){ int ne=e[j].to; if (v[ne])continue; int x=find(e[j].from),y=find(ne); if (x!=y){ num++; f[x]=f[y]; } } ans[i]=n-i-num; } for (int i=0;i<=k;i++)printf("%d ",ans[i]); return 0; }