https://www.luogu.org/problemnew/show/P1197

題解：倒向并查集

C++版本一

#include<iostream> #include<cstdio> #define f(i,a,b) for(register int i=a;i<=b;i++) #define fd(i,a,b) for(register int i=a;i>=b;i--) using namespace std; int k,n,m,head[400002],tot,broken[400002],ans[400003]; int father[400003]; struct Node {int next,node,from; }h[400002]; inline void Add_Node(int u,int v) {h[++tot].from=u;h[tot].next=head[u];head[u]=tot;h[tot].node=v; } bool Broken[400001]; inline int Get_father(int x) {if(father[x]==x) return x;return father[x]=Get_father(father[x]);//你爸爸的爸爸就是你的爸爸——反查理馬特——并查集 } inline void hb(int u,int v) {u=Get_father(u),v=Get_father(v);if(u!=v) father[v]=u; } int main() {ios::sync_with_stdio(false);cin>>n>>m;f(i,0,n)father[i]=i,head[i]=-1;//并查集初始化 f(i,1,m){int x,y;cin>>x>>y;Add_Node(x,y);//儲(chǔ)存圖 Add_Node(y,x);//由于無向圖存兩遍 }cin>>k;f(i,1,k){cin>>broken[i];Broken[broken[i]]=1;//標(biāo)記砸壞了 }int total=n-k;//初始化為所有點(diǎn)都是單獨(dú)存在的 f(i,1,2*m)//有2*m個(gè)邊 if(!Broken[h[i].from] && !Broken[h[i].node] && Get_father(h[i].from)!=Get_father(h[i].node)) {//要是起點(diǎn)和終點(diǎn)都沒砸壞 而且他們并沒有聯(lián)通total--;//連一條邊 減一個(gè)聯(lián)通體 hb(h[i].from,h[i].node);}ans[k+1]=total;//當(dāng)前就是最后一次破壞后的個(gè)數(shù) fd(i,k,1){//total=0 //這里不需要初始化 需要從上一次的廢墟上修建 total++;//修復(fù)一個(gè)點(diǎn) 聯(lián)通體+1 Broken[broken[i]]=0;//修復(fù) for(int j=head[broken[i]];j!=-1;j=h[j].next)//枚舉每一個(gè)子點(diǎn) {if(!Broken[h[j].node] && Get_father(broken[i])!=Get_father(h[j].node)){total--;//連一邊減一個(gè)聯(lián)通塊 hb(broken[i],h[j].node);//合并這兩個(gè)點(diǎn) }}ans[i]=total;}f(i,1,k+1) cout<<ans[i]<<endl;return 0; }

C++版本二

/* *@Author: STZG *@Language: C++ */ #include <bits/stdc++.h> #include<iostream> #include<algorithm> #include<cstdlib> #include<cstring> #include<cstdio> #include<string> #include<vector> #include<bitset> #include<queue> #include<deque> #include<stack> #include<cmath> #include<list> #include<map> #include<set> //#define DEBUG #define RI register int using namespace std; typedef long long ll; //typedef __int128 lll; const int N=400000+10; const int M=100000+10; const int MOD=1e9+7; const double PI = acos(-1.0); const double EXP = 1E-8; const int INF = 0x3f3f3f3f; int t,n,m,k,q; int ans[N],cnt,flag,temp,sum; vector<int>G[N]; int broken[N]; bool Broken[N]; int pre[N]; char str; struct node{}; int find(int x){return (pre[x]==x)?x:pre[x]=find(pre[x]);} int main() { #ifdef DEBUGfreopen("input.in", "r", stdin);//freopen("output.out", "w", stdout); #endif//ios::sync_with_stdio(false);//cin.tie(0);//cout.tie(0);//scanf("%d",&t);//while(t--){scanf("%d%d",&n,&m);for(int i=0;i<n;i++){pre[i]=i;}int x,y;for(int i=1;i<=m;i++){scanf("%d%d",&x,&y);G[x].push_back(y);G[y].push_back(x);}scanf("%d",&k);cnt=n-k;for(int i=1;i<=k;i++){scanf("%d",&broken[i]);Broken[broken[i]]=1;}for(int i=0;i<n;i++){for(int j=0,sz=G[i].size();j<sz;j++){int u=i;int v=G[i][j];int tx=find(u);//cout<<u<<" ";int ty=find(v);//cout<<v<<endl;if(!Broken[u]&&!Broken[v]&&tx!=ty){cnt--;pre[tx]=ty;}}}ans[k+1]=cnt;for(int i=k;i>=1;i--){cnt++;Broken[broken[i]]=0;for(int j=0,sz=G[broken[i]].size();j<sz;j++){int u=broken[i];int v=G[broken[i]][j];//cout<<j<<" ";int tx=find(u);//cout<<u<<" ";int ty=find(v);//cout<<v<<endl;if(!Broken[u]&&!Broken[v]&&tx!=ty){cnt--;pre[tx]=ty;}}ans[i]=cnt;}for(int i=1;i<=k+1;i++){cout<<ans[i]<<endl;}//}#ifdef DEBUGprintf("Time cost : %lf s\n",(double)clock()/CLOCKS_PER_SEC); #endif//cout << "Hello world!" << endl;return 0; }

?

總結(jié)

以上是生活随笔為你收集整理的[JSOI2008]星球大战的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

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