题目描述
由于并查集不支持删除操作,这里可以逆向思维一波,使用反向并查集,
如果按照正序,求打击一次,二次连通块的数目,会超时,此时可以求将k次全部打击完的连通块数目,
接着将k-1次打击的点补上求连通块数目,一直补到第0次打击的数目,然后逆序输出就可。
样例
8 13
0 1
1 6
6 5
5 0
0 6
1 2
2 3
3 4
4 5
7 1
7 2
7 6
3 6
5
1
6
3
5
7
输出
1
1
1
2
3
3
#include<iostream>
using namespace std;
const int N =400010;
int head[N],ans[N],p[N],d[N],idx=0;//头节点,答案,父亲,打击点
bool e[N];//是否被打击
//邻接表
struct edge{int u,v,next;}ed[400010];
//并查集
int find(int x)
{
if(x!=p[x])p[x]=find(p[x]);
return p[x];
}
//邻接表插入
void insert(int u,int v)
{
ed[idx].u=u;
ed[idx].v=v;
ed[idx].next = head[u];
head[u]=idx++;
}
int main()
{
int n,m,k,tol,x,y,u;
cin>>n>>m;
//初始化
for(int i=0;i<n;++i)
{
head[i]=-1;
p[i]=i;
}
//m个点连接
for(int i=0;i<m;++i)
{
cin>>x>>y;
insert(x,y);
insert(y,x);
}
cin>>k;
tol = n-k;//打击k次后的点
//记录打击
for(int i =1;i<=k;++i)
{
cin>>x;
d[i] =x;
e[x]=true;
}
//先连通没有被打击的点
for(int i =0;i<2*m;++i)
{
if(!e[ed[i].u]&&!e[ed[i].v])
{
int s = find(ed[i].u),t=find(ed[i].v);
if(s!=t)
{
tol--;
p[find(ed[i].u)]=find(ed[i].v);
}
}
}
//再一个个连接打击点
ans[k+1]=tol;//打击k次的连通块
//从打击k次算打击k-1次一直算到打击0次
for(int j=k;j>=1;j--)
{
//修复点
u=d[j];
e[u]=false;
tol++;
//修复连接所有它所连接的点
for(int i=head[u];i!=-1;i=ed[i].next)
{
if(!e[ed[i].v]&&find(ed[i].v)!=find(u))
{
tol--;
p[find(ed[i].v)]=find(u);
}
}
ans[j]=tol;
}
for(int i=1;i<=k+1;++i) cout<<ans[i]<<endl;
return 0;
}