本文共 2352 字，大约阅读时间需要 7 分钟。

什么是并查集？

【普通并查集】

【How Many Tables】

Problem Description

Lh Boy无聊的时候很喜欢数蚂蚁，而且，还给每一只小蚂蚁编号，通过他长期的观察和记录，发现编号为i的蚂蚁会和编号为j的蚂蚁在一起。

Input

第一行输入一个整数T，表示有T(1<=T<=25)组测试案例。每一组测试案例，先输入两个整数N和M，分别表示蚂蚁的总数（编号分别为1~N）和记录的条数(1<=N,M<=1000)。紧接着有M行，每一行输入两个数字，a b，表示编号a和编号b的蚂蚁在同一堆里面。在每组测试案例之间都会输入一行空行。

Output

对于每组测试案例，在一行中输出答案。

【...】

跟之前相比区别在于Find函数写成递归的形式简短了很多（笑）。

【代码】

int pre[1005];int Find(int x){return pre[x]==x?x:pre[x]=Find(pre[x]);}void join(int x,int y){    x=Find(x),y=Find(y);    if(x!=y) pre[x]=y;}int main(){    int t; scanf("%d",&t);    for(int k=0;k

【带删除并查集】

上边的并查集主要是用到了增，那么提到删，比如说删除u和指向节点v之间的联系，我们可能会下意识的觉得只要使u重新指向自己即可，但是这种做法是不对的。在实际情况中，我们的并查集形成的树的形态都是不可预估形态的，如果直接将节点u指向自己，可能会将u的下级和u一块删除。所以需要处理一下：

定义一个数组f[]存放虚根，f[i]存放的是元素 i 的编号，这个编号在程序运行过程中是逐渐变化的。

当删除了 元素 i 以后，将元素 i 的编号更改为当前最大的编号+1(pos)，再把pre[i]赋值为新的f[i]。

这样可以使得元素 i 原先的同组元素不受影响，且元素 i 被分配到一个只包含元素 i 的新组。

这里提到了一个虚根的概念，意思就是在删除节点u的时候，使节点u的虚根f[u]指向一个不存在的节点，而pre[u]不做改动，从而既删除了节点u，又不影响u的同组元素。

【例题】

【...】

居然RE了一发，懵了一下然后发现因为虚根最多可能到1e6，一开始开到1e5+5不够用，可能会数组越界。

const int maxn=1e6+5;const int inf=0x3f3f3f3f;const int mod=1e9+7;int pre[maxn],f[maxn],vis[maxn];int pos;int Find(int x){return pre[x]==x?x:pre[x]=Find(pre[x]);}void join(int x,int y){x=Find(x),y=Find(y);if(x!=y) pre[x]=y;}void del(int x){    f[x]=pos;    pre[pos]=pos;    pos++;}int main(){    int n,m,t=0;    while(~scanf("%d%d",&n,&m))    {        if(n==0&&m==0) break;        pos=n;        for(int i=0;i

【关系并查集】

带关系的并查集。

【例题】

【题意】

输入恋爱关系，判断是否存在同性恋。

【代码】

#define go(i,a,b) for(int i=a;i<=b;i++)#define og(i,a,b) for(int i=a;i>=b;i--)#define mem(a) memset(a,0,sizeof(a))using namespace std;int pre[2005],r[2005],f;int Find(int x){    if(x==pre[x]) return x;    int t=Find(pre[x]); //寻找祖先    r[x]=(r[x]+r[pre[x]])%2;    return pre[x]=t;}void join(int x,int y){    int fx=Find(x),fy=Find(y);    if(fx==fy)    {        if(r[x]==r[y]) f=1;        return;    }    pre[fx]=fy;    r[fx]=(r[x]+r[y]+1)%2; //相邻不同性别}int main(){    int t; scanf("%d",&t);    while(t--)    {        f=0;        int n,m; scanf("%d%d",&n,&m);        go(i,1,n) pre[i]=i,r[i]=0;        while(m--)        {            int a,b; scanf("%d%d",&a,&b);            if(f) continue;            else join(a,b);        }        if(f) puts("Suspicious bugs found!");        else puts("No suspicious bugs found!");    }    return 0;}

转载地址：http://eyben.baihongyu.com/