BZOJ 1015: [JSOI2008]星球大战starwar【并查集】
题目可以表述成：给定一个无向图G，每次删除它的一个点和与点相关的边集，每次询问该操作后图G的连通度（连通分量的个数）。和上一题一样都是考察逆向思维，虽然删除点的做法不会，但是每次加点后询问连通度却是并查集的经典用法，所以答案可以逆过来推，具体做的时候每次加入一个点，将所有和这个点有边相连的点集合并，然后输出当前有多少个集合。细节部分需要注意的是由于点的数量十分庞大，邻接表是十分有必要的
#include<iostream>
#include<cstdio>
#include <math.h>
using namespace std;
intfather[400001]={0},next[400001]={0},point[400001]={0},root[400001]={0},now=0;
bool h[400001]={false};
void add(int a,int b)
{
now++;
point[now]=a;
next[now]=root[b];
root[b]=now;
}
int find(int v)
{
if(v==father[v])return v;
return father[v]=find(father[v]);
}
void unio(int a,int b)
{
father[find(a)]=father[find(b)];
}
int main()
{
int n,m,t,x[400001]={0},y[400001]={0},k,a[400001]={0},ans[400001]={0},j;
scanf("%d%d",&n,&m);
for (int i=1;i<=n;i++)father[i]=i;//初始化并查集
for (int i=1;i<=m;i++)
{
scanf("%d%d",&x[i],&y[i]);
add(x[i],y[i]);
add(y[i],x[i]);//邻接表
}
scanf("%d",&k);
t=n-k;
for (int i=1;i<=k;i++)
{
scanf("%d",&a[k-i+1]);
h[a[k-i+1]]=true;
}
for (int i=1;i<=m;i++)
if((h[x[i]]==false)&&(h[y[i]]==false)&&(find(x[i])!=find(y[i])))
{
unio(x[i],y[i]);t--;
}
ans[0]=t;
for (int i=1;i<=k;i++)
{
t++;
h[a[i]]=false;
j=root[a[i]];
while (j!=0)
{
if ( find(point[j])!=find(a[i]) && (h[point[j]]==false) )
{
unio(point[j],a[i]);
t--;
}
j=next[j];
}
ans[i]=t;
}
for (inti=k+1;i>=1;i--)printf("%d\n",ans[i-1]);
return 0;
}
郑重声明：本站内容如果来自互联网及其他传播媒体，其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享，并不代表本站赞同其观点和对其真实性负责，也不构成任何其他建议。
