題目大意

　　給你一張\(n\)個(gè)點(diǎn)\(m\)條邊的無向圖，有\(q\)次操作，每次刪掉一個(gè)點(diǎn)以及和這個(gè)點(diǎn)相鄰的邊，求最開始和每次刪完點(diǎn)后的連通塊個(gè)數(shù)。

　　\(q\leq n\leq 400000,m\leq 200000\)

題解

　　我們可以用并查集維護(hù)連通塊個(gè)數(shù)，可惜并查集不支持刪除操作。

　　但是這道題沒有強(qiáng)制在線，所以可以先刪完所有點(diǎn)后再一個(gè)個(gè)加回來。

　　加邊的時(shí)候維護(hù)連通塊個(gè)數(shù)。

　　時(shí)間復(fù)雜度：\(O(n\alpha(n))\)

代碼

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cstdlib>
#include<ctime>
#include<utility>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
struct graph
{int v[1000010];int t[1000010];int h[1000010];int n;graph(){n=0;memset(h,0,sizeof h);}void add(int x,int y){n++;v[n]=y;t[n]=h[x];h[x]=n;}
};
graph g;
int f[1000010];
int b[1000010];
int x[1000010];
int y[1000010];
int c[1000010];
int s[1000010];
int r[1000010];
int find(int x)
{return f[x]==x?x:f[x]=find(f[x]);
}
int merge(int x,int y)
{x=find(x);y=find(y);if(x==y)return 0;if(r[x]>r[y])swap(x,y);f[x]=y;if(r[x]==r[y])r[y]++;return 1;
}
int main()
{int n,m;scanf("%d%d",&n,&m);int i;for(i=1;i<=n;i++){b[i]=1;f[i]=i;r[i]=1;}for(i=1;i<=m;i++){scanf("%d%d",&x[i],&y[i]);x[i]++;y[i]++;g.add(x[i],y[i]);g.add(y[i],x[i]);}int q;scanf("%d",&q);int ans=n;for(i=1;i<=q;i++){scanf("%d",&c[i]);c[i]++;b[c[i]]=0;ans--;}int j;for(i=1;i<=n;i++)if(b[i])for(j=g.h[i];j;j=g.t[j])if(b[g.v[j]])ans-=merge(i,g.v[j]);s[q]=ans;for(i=q;i>=1;i--){b[c[i]]=1;ans++;for(j=g.h[c[i]];j;j=g.t[j])if(b[g.v[j]])ans-=merge(c[i],g.v[j]);s[i-1]=ans;}for(i=0;i<=q;i++)printf("%d\n",s[i]);return 0;
}

轉(zhuǎn)載于:https://www.cnblogs.com/ywwyww/p/8513308.html

總結(jié)

以上是生活随笔為你收集整理的【BZOJ1015】【JSOI2008】星球大战 并查集的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。