并查集学习心得

int find(int x)//并查集找父亲
{if(x!=fa[x]) fa[x]=find(fa[x]);return fa[x];
}
void add(int x,int y)//合并 
{int fx=find(x);int fy=find(y);if(x!=y) fa[fx]=fy;
}

P1197 [JSOI2008] 星球大战 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

洛谷p1197星球大战 :并查集+逆向思考_phrame_的博客-CSDN博客

这题由于并查集不好进行删除点的操作，所以反向操作，把删除点反向成一个个添加新的点，注意判断连通块的方法是看，fa[i]==i，那么是一个连通块，父亲相等为一个连通块

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e6+100;
vector<int>ans;
vector<int> a[N];//存图
int fa[N];
int h[N];//存要摧毁的 
int vis[N];//标记是否要摧毁 
int find(int x)//并查集 
{if(x!=fa[x]) fa[x]=find(fa[x]);return fa[x];
}
void add(int x,int y)//合并 
{int fx=find(x);int fy=find(y);if(x!=y) fa[fx]=fy;
}
signed main()
{int n,m;cin>>n>>m;for(int i=0;i<n;i++){fa[i]=i;//初始化 }for(int i=1;i<=m;i++){int u,v;cin>>u>>v;a[u].push_back(v);a[v].push_back(u);//双向存图 }int k;cin>>k;for(int i=1;i<=k;i++){cin>>h[i];vis[h[i]]=1;//标记要摧毁的 }for(int i=0;i<n;i++){for(auto x:a[i])//遍历a[i]所有的点 {if(vis[x] ||vis[i])//去掉要摧毁的 {continue;}add(x,i);//对不摧毁的点合并处理 }}int cnt=0;for(int i=0;i<n;i++){if(!vis[i]&&fa[i]==i){cnt++;//没有修复前连通块的个数 }} ans.push_back(cnt);//最后一种全摧毁完的答案//开始修复，倒推for(int i=k;i>=1;i--){int x=h[i];cnt++;//把它当成独立的连通块 vis[x]=0;//被修复 for(auto u:a[x]){if(!vis[u]&&find(x)!=find(u)){add(u,x); cnt--;//减去不是连通块的 }}ans.push_back(cnt);} reverse(ans.begin(),ans.end());for(auto c:ans) {cout<<c<<endl;}return 0;
}