NOIP2016回来以后正式上的第一节课。先贴定义
总的来说，并查集是相对来说好理解的一种数据处理方法。先看一道裸并查集。（洛谷链接：https://www.luogu.org/problem/show?pid=1551）。程序如下，写得可能不够简洁，但是还是可以看出并查集大致的过程。
#include<iostream> #include<cstdio> using namespace std; int fa[5050],deep[5050],n,m,p; int getf(int k){ //寻找该节点的父节点，这里涉及到一个优化，路径压缩。即每次寻找一个节点的“祖先”时，直接将改点指向“祖先”（把父节点更新为“祖先”） if(k!=fa[k])fa[k]=getf(fa[k]); return fa[k]; } void tog(int x,int y){ //“并”的过程 int fx=getf(x); int fy=getf(y); fa[fx]=fy; if(deep[x]==deep[y]){ //deepi记录节点的深度，这里涉及到另一个优化，按RANK合并。将高度低的树合并到高度高的树上，使整棵树的高度更低（虽然不如路径压缩有效） deep[x]++; deep[y]++; } else deep[x]=deep[y]; } int main(){ cin>>n>>m>>p; for(int i=1;i<=n;++i){ deep[i]=1; fa[i]=i; } for(int i=1;i<=m;++i){ int x,y; scanf("%d%d",&x,&y); if(fa[x]!=fa[y]){ if(deep[x]<deep[y])tog(x,y); else tog(y,x); } } for(int i=1;i<=n;++i)fa[i]=getf(i); for(int i=1;i<=p;++i){ int x,y; scanf("%d%d",&x,&y); if(fa[x]==fa[y])cout<<"Yes"; else cout<<"No"; cout<<endl; } return 0; }
由此可见，裸的并查集是十分简单的。
同时，并查集涉及到一个最小生成树的算法——kruskal算法，其原理是将连通图中所有的边按照从小到大排序，取其中有意义的（既当前状态下这条边是否连通会影响图的连通状态的边）且长度最小的边，加入图中，当所有N个点都连通（即加入第N-1条边时），既完成了最小生成树的生成。
洛谷题目链接：https://www.luogu.org/problem/show?pid=3366 程序如下
#include<iostream> #include<cstdio> #include<algorithm> using namespace std; struct edge{ int power; int point1; int point2; }; edge a[200010]; int m,n,f[5000]; int comp(const edge&a,const edge&b){ return(a.power<b.power); } void readit(){ cin>>n>>m; for(int i=1;i<=n;++i)f[i]=i; for(int i=1;i<=m;++i){ scanf("%d%d%d",&a[i].point1,&a[i].point2,&a[i].power); } sort(a+1,a+m+1,comp); return; } int findf(int k){ if(f[k]!=k)f[k]=findf(f[k]); return f[k]; } void kruskal(){ int ans=0; for(int i=1;i<=m;++i){ int f1=findf(a[i].point1); int f2=findf(a[i].point2); if(f1!=f2){ ans+=a[i].power; f[f[f1]]=f[f2]; } } cout<<ans; return; } int main(){ readit(); kruskal(); return 0; }
并查集并不是所有时候都十分简易的。比如经典题目“食物链”（洛谷链接：https://www.luogu.org/problem/show?pid=2024）
首先看到题目，偷瞄一眼标签可以发现这是一道并查集，细想的确：当两种动物不在同一个集合中时，说的话必定是真话。首先分析，动物没有确定的种类，所以直接认定某个动物是A,B或C都无所谓，因此果断设第一个读进来的动物为A，然后。。。。。。其实我们不难发现必须保存一种关系，使得两棵树在合并之后能够重新得到每种动物之间的关系。而并查集中一般会保存例如深度。。。。。。就可以想到利用深度来保存某个点与根节点的关系——如当动物X,Y同为一个物种，设Y为X的父节点，则可以设边XY权值为0，deepx=deepy；当X吃Y时，设Y为X的父节点。边XY=1，deepx=deepy+1;同理，当Y吃X时，设Y为X的父节点，边XY=2，deepx=deepy+2；这样，通过判断两个节点对3取模的余数，就可以轻易判断出两个物种之间的关系：①deepx%3=deepy%3,X，Y为同一物种；②deepx%3=(deepy+1)%3,Y吃X；③deepx%3=(deepy+2)%3,X吃Y。
程序如下：
#include<iostream> #include<cstdio> using namespace std; int fa[50050],deep[50050],n,k; int getf(int k){ if(k!=fa[k]){ int t=fa[k]; fa[k]=getf(fa[k]); deep[k]=(deep[k]+deep[t])%3; } return fa[k]; } int main(){ cin>>n>>k; for(int i=1;i<=n;++i){ fa[i]=i; deep[i]=0; } int ans=0; for(int i=1;i<=k;++i){ int d,x,y; scanf("%d%d%d",&d,&x,&y); if((x>n)||(y>n)){ans++;continue;} if(d==1){ if(getf(x)==getf(y)) if(deep[x]!=deep[y]){ans++;} if(fa[x]!=fa[y]){ deep[fa[x]]=(deep[y]-deep[x]+3)%3; fa[fa[x]]=fa[y]; } } if(d==2){ if(x==y){ans++; continue;} if(getf(x)==getf(y)) if(deep[x]!=(deep[y]+1)%3){ans++;} if(fa[x]!=fa[y]){ deep[fa[x]]=(deep[y]-deep[x]+4)%3; fa[fa[x]]=fa[y]; } } } cout<<ans; return 0; }
To be continued......