并查集

prediction

2026-09-27 09:30:22

发布于：浙江

34阅读

0回复

0点赞

一些神秘的trick（比如离线加边这种东西）我就不讲了，因为我还没学会。

大家都知道我写过MST，那里就有一个叫 $fa$ 的数组，这个是用来干嘛的呢？

$fa$ 不难看出是 $father$ 的缩写，所以这玩意就是用来存父节点的，当然，我们后面会通过路径压缩来做到用 $fa$ 来表示根结点，都说到路径压缩了，那么我们就写出来看看。

int find(int x)
{
    if(x!=fa[x]) fa[x]=find(fa[x]);
    return fa[x];
}

很简单对吧，首先 if 里放的就是判断是否为根，因为根结点的 $fa$ 就是它自己，这个在初始化的时候会讲到，不是的话就继续找，最后返回的自然就是这个并查集的根。

通过这一点，我们可以知道一个小trick的解法，也就是并查集的总个数 $=$ 元素等于它的 $fa$ 值的元素的个数。

这就是基本的路径压缩，也就是不断递归找到这个并查集的根。

当然你看到了MST里的 find 也就会看到 unite，这也是一个函数，就是用来合并的。

void unite(int x,int y)
{
    x=find(x);
    y=find(y);
    if(x!=y) fa[y]=x;
}

是不是很简单，首先找到根，如果根不一样就把 $y$ 的父节点（注意这里的 $y$ 是原来 $y$ 的根）变成 $x$ （同理这里也是根），相当于把 $y$ 所在的并查集合并到了 $x$ 的并查集去。

这就是一个初步的认识，我们可以写模板了。

P3367 【模板】并查集

显然在 $z=2$ 时调用 find 查根就行了，所以黄++。

#include <iostream>
using namespace syh;
int fa[200005], n, m;
int find(int x)
{
    if(fa[x]!=x) fa[x]=find(fa[x]);
    return fa[x];
}
void unite(int x,int y)
{
    x=find(x);
    y=find(y);
    if(x!=y) fa[y]=x;
}
int main()
{
    cin>>n>>m;
    for(int i = 1;i<=n;i++) fa[i]=i;
    while(m--)
    {
        int z, x, y;
        cin>>z>>x>>y;
        if(z==1) unite(x,y);
        else cout<<(find(x)==find(y)?"Y":"N")<<"\n";
    }
}

很显然这种东西也可以出的不明显一点。

P1551 亲戚

这里的“亲戚关系”就可以看做是在一个并查集里的，只要知道了这点，那么这道题就可以当板子做，黄++。

#include <iostream>
using namespace syh;
int fa[5005];
int n, m, p;
int find(int x)
{
    if(x!=fa[x]) fa[x]=find(fa[x]);
    return fa[x];
}
void unite(int x,int y)
{
    x=find(x);
    y=find(y);
    if(x!=y) fa[y]=x;
}
int main()
{
    cin>>n>>m>>p;
    for(int i = 1;i<=n;i++) fa[i]=i;
    for(int i = 1;i<=m;i++)
    {
        int x, y;
        cin>>x>>y;
        unite(x,y);
    }
    while(p--)
    {
        int pi, pj;
        cin>>pi>>pj;
        if(find(pi)==find(pj)) cout<<"Yes\n";
        else cout<<"No\n";
    }
}

之前说到了一个小trick，前两天翻到了一道与之匹配题目，放一下。

P14077 [GESP202509 七级] 连通图

首先看下重边与自环，你可以自己探究一下，其实这两个东西在并查集里都可以被忽略，反正边都在并查集里就算是环也可以看做一个并查集。

所以，我们需要加的边数，就可以看做是把这几个连通块连起来的边数，也就是连通块数量 $-1$ ，那这个数量怎么求呢？我们可以用 if(fa[i]==i) 来判断根，一个根对应的就是一个连通块，最后数量 $-1$ 就是答案。

#include <iostream>
using namespace syh;
int fa[100005], n, m, ans=0;
int find(int x)
{
    if(x!=fa[x]) fa[x]=find(fa[x]);
    return fa[x];
}
void unite(int x,int y)
{
    x=find(x);
    y=find(y);
    if(x!=y) fa[y]=x;
}
int main()
{
    cin>>n>>m;
    for(int i = 1;i<=n;i++) fa[i]=i;
    for(int i = 1;i<=m;i++)
    {
        int u, v;
        cin>>u>>v;
        unite(u,v);
    }
    for(int i = 1;i<=n;i++)
    {
        if(fa[i]==i) ans++;
    }
    cout<<ans-1;
}

并查集还可以与MST结合。

P1669 [USACO04DEC] Bad Cowtractors S

有道更好的找不到了，这个之前在MST里也写了。

我们可以看出这道题就是求一个最大的生成树边权和，但是我们在这里不需要关注它，因为我写的是并查集。这里我们只需要知道并查集是怎么在MST里工作的就行，它起到一个装生成树的作用，如果你选了一条边，那么你就要把它装进这个生成树，所以好像~~挺简单的？~~

放下代码吧。

#include <iostream>
#include <algorithm>
#include <vector>
using namespace syh;
const int maxn=1005;
struct edge
{
    int u, v, w;
    bool operator>(const edge &b) const
    {
        return w>b.w;
    }
};
int fa[maxn];
int n, m;
vector<edge> e;
int find(int x)
{
    if(fa[x]!=x) fa[x]=find(fa[x]);
    return fa[x];
}
void unite(int x,int y)
{
    x=find(x);
    y=find(y);
    if(x!=y) fa[y]=x;
}
int main()
{
    cin>>n>>m;
    for(int i = 1;i<=n;i++) fa[i]=i;
    for(int i = 1;i<=m;i++)
    {
        int x, y, z;
        cin>>x>>y>>z;
        e.push_back({x,y,z});
    }
    sort(e.begin(),e.end(), greater<edge>());
    int ans=0, cnt=0;
    for(auto &edg:e)
    {
        int u=edg.u, v=edg.v, w=edg.w;
        if(find(u)!=find(v))
        {
            unite(u,v);
            ans+=w;
            cnt++;
            if(cnt==n-1) break;
        }
    }
    if(cnt==n-1) cout<<ans;
    else cout<<"-1";
}

其实这个代码也没那么重要，因为是MST的，这道题就是给大家看一下并查集怎么在MST里用。

接下来我们可以迎接两个新的知识点了，边带权与扩展域。

这里没有可持久化并查集，因为我太菜了。

首先是扩展域。（不要学我傻傻的先学边带权）

它名字叫这个，肯定是要把并查集的这个“集”扩大（~~我说啥呢~~），所以在初始化的时候需要根据题目来搞。

它比较适合解决a吃b，b吃c，c吃a这种食物链的问题。

具体方法就是把朋友放一类并查集，敌人放一类并查集。

P2024 [NOI2001] 食物链

我们判断的是假话的总数，所以我们就是要去把每个可能为假话的可能性都看一遍。

所以我们有了已下代码：

#include <iostream>
using namespace syh;
int n, k, ans=0, fa[150005];
int find(int x)
{
    if(x!=fa[x]) fa[x]=find(fa[x]);
    return fa[x];
}
void unite(int x,int y)
{
    x=find(x);
    y=find(y);
    if(x!=y) fa[y]=x;
}
int main()
{
    cin>>n>>k;
    for(int i = 1;i<=n*3;i++) fa[i]=i;
    while(k--)
    {
        int op, x, y;
        cin>>op>>x>>y;
        if(op==1)
        {
        }
        else
        {
        }
    }
    cout<<ans;
}

只是不知道里面写啥。

接着我们知道假话可以看做一个真话的 $!=$ ，所以有了：

#include <iostream>
using namespace syh;
int n, k, fa[150005], ans=0;
int find(int x)
{
    if(x!=fa[x]) fa[x]=find(fa[x]);
    return fa[x];
}
void unite(int x,int y)
{
    x=find(x);
    y=find(y);
    if(x!=y) fa[y]=x;
}
int main()
{
    cin>>n>>k;
    for(int i = 1;i<=n*3;i++) fa[i]=i;
    while(k--)
    {
        int op, x, y;
        cin>>op>>x>>y;
        if(x>n||y>n)
        {
            ans++;
            continue;
        }
        if(op==1)
        {
            if(find(x)!=find(y)) 
            {
                ans++;
                continue;
            }
            else
            {
                unite(x,y);
                unite(x+n,y+n);
                unite(x+n*2,y+n*2);
            }
        }
        else
        {
            if(find(x)!=find(y+n))
            {
                ans++;
                continue;
            }
            else
            {
                unite(x+n,y);
                unite(y+n*2,x);
                unite(x+n*2,y+n);
            }
        }
    }
    cout<<ans;
}

然后就得到了：

这是因为我们的判断条件可能有误差，万一没有这个关系的话，ans还是会把这句话算成假话，所以要修改一下，改成判断是不是其余两种情况。

#include <iostream>
using namespace syh;
int n, k, ans=0, fa[150005];
int find(int x)
{
    if(x!=fa[x]) fa[x]=find(fa[x]);
    return fa[x];
}
void unite(int x,int y)
{
    x=find(x);
    y=find(y);
    if(x!=y) fa[y]=x;
}
int main()
{
    cin>>n>>k;
    for(int i = 1;i<=n*3;i++) fa[i]=i;
    while(k--)
    {
        int op, x, y;
        cin>>op>>x>>y;
        if(x>n||y>n)
        {
            ans++;
            continue;
        }
        if(op==1)
        {
            if(find(x)==find(y+n)||find(x)==find(y+n*2))
            {
                ans++;
                continue;
            }
            else
            {
                unite(x,y);
                unite(x+n,y+n);
                unite(x+n*2,y+n*2);
            }
        }
        else
        {
            if(find(x)==find(y)||find(x)==find(y+n))
            {
                ans++;
                continue;
            }
            else
            {
                unite(x,y+n*2);
                unite(x+n,y);
                unite(x+n*2,y+n);
            }
        }
    }
    cout<<ans;
}

P1892 [BalticOI 2003] 团伙 (Day 2)

这个题目和上面的几乎一样，甚至可以说是简化版，所以绿++。

#include <iostream>
using namespace syh;
int fa[2005], n, m, ans=0;
int find(int x)
{
    if(x!=fa[x]) fa[x]=find(fa[x]);
    return fa[x];
}
void unite(int x,int y)
{
    x=find(x);
    y=find(y);
    if(x!=y) fa[y]=x;
}
int main()
{
    cin>>n>>m;
    for(int i = 1;i<=n*2;i++) fa[i]=i;
    for(int i = 1;i<=m;i++)
    {
        char op;
        int p, q;
        cin>>op>>p>>q;
        if(op=='F') unite(p,q);
        else 
        {
            unite(p,q+n);
            unite(q,p+n);
        }
    }
    for(int i = 1;i<=n;i++)
    {
        if(find(i)==i) ans++;
    }
    cout<<ans;
}

当然，unite(p,q+n);unite(q,p+n); 两段才是我们要说的。

我们回到那个 unite 函数，可以看到这段函数是把 $y$ 接在 $x$ 后面，所以代码的意思就是把q+n 接到 p 后，这样才能在统计的时候把这个并查集统计进去，因为我们统计的时候并不会把扩展的虚拟并查集算进去，因此，我们就不能写 unite(q+n,p);unite(p+n,q);，因为这样不会被统计到。

边带权。

其实就是加一个 $d$ 数组来记录每个权值（子到父节点），因此我们的 find 要改成：

int find(int x)
{
    if(x!=fa[x])
    {
        int ofa=fa[x];
        fa[x]=find(fa[x]);
        //fa[ofa]已改变
        d[x]+=d[ofa];//x连根
    }
    return fa[x];
}

$d[x]$ 先是 $x$ 到 $fa[x]$ 的权值，在 $fa[x]$ 变成根后， $d[fa[x]]$ 也会变为 $d[fa[x]]$ 到根，这个时候把两个值加在一起就有了 $x$ 到根的权值。

unite 函数也要变，但是需要看题目对症下药，那就来看题目吧。

P1196 [NOI2002] 银河英雄传说

我们来讲讲 unite。

这道题的输出要告诉机子 $i-j$ 有多少战舰，我们不放开一个 $f$ 数组记录每个战舰前面战舰的台数，在合并的时候，由于 $x$ 被接到 $y$ 后面，所以原来的 $d[x]$ 就是它前面的 $f[y]$ 的数量，因为现在 $x$ 放进来了，所以我们再去更新 $f[y]$ 就行。

void unite(int x,int y)
{
    int rx=find(x), ry=find(y);
    if(rx!=ry)
    {
        fa[rx]=ry;
        d[rx]=f[ry];
        f[ry]+=f[rx];
    }
}

于是有了已下代码：

#include <iostream>
using namespace syh;
int t, fa[30005], d[30005], f[30005];
int find(int x)
{
    if(x!=fa[x])
    {
        int ofa=fa[x];
        fa[x]=find(fa[x]);
        //fa[ofa]已改变
        d[x]+=d[ofa];//x连根
    }
    return fa[x];
}
void unite(int x,int y)
{
    int rx=find(x), ry=find(y);
    if(rx!=ry)
    {
        fa[rx]=ry;
        d[rx]=f[ry];
        f[ry]+=f[rx];
    }
}
int main()
{
    cin>>t;
    for(int i = 1;i<=30000;i++)
    {
        fa[i]=i;
        f[i]=1;//并查集本来就一个自己
        d[i]=0;
    }
    while(t--)
    {
        char op;
        int x, y;
        cin>>op>>x>>y;
        if(op=='M')
        {
            unite(x,y);
        }
        else
        {
            if(find(x)==find(y))
            {
                cout<<abs(d[x]-d[y])-1<<'\n';//注意减掉自身的一个
            }
            else cout<<"-1\n";
        }
    }
}

如果你不理解那我们可以换一道题目，其实就是一个双倍经验。

P5092 [USACO04OPEN] Cube Stacking

这里的关系就很明显了，移动的时候在 $x$ 下面的就是原来 $y$ 的总积木数，就是 $f[y]$ ，移动完后 $y$ 的总积木数还要加上 $x$ 的总积木数。

#include <iostream>
using namespace syh;
int p, fa[30005], d[30005], f[30005];
int find(int x)
{
    if(x!=fa[x])
    {
        int ofa=fa[x];
        fa[x]=find(fa[x]);
        d[x]+=d[ofa];
    }
    return fa[x];
}
void unite(int x,int y)
{
    int rx=find(x), ry=find(y);
    if(rx!=ry)
    {
        fa[rx]=ry;
        d[rx]=f[ry];
        f[ry]+=f[rx];
    }
}
int main()
{
    cin>>p;
    for(int i = 1;i<=30000;i++)
    {
        fa[i]=i;
        d[i]=0;
        f[i]=1;
    }
    while(p--)
    {
        char op;
        int x;
        cin>>op>>x;
        if(op=='M')
        {
            int y;
            cin>>y;
            unite(x,y);
        }
        else
        {
            find(x);//更新d[x]（到根）
            cout<<d[x]<<'\n';
        }
    }
}

这里要 find 一下，因为我们之前在写上一题的时候已经在 if 里隐式调用了。（不find就没有最后的x到根的个数）

有帮助，赞一个

去预览

0/2000

全部评论 6

请‎输‎入‎文‎本‎. ‎🐛‎
您怎么这么强

1周前来自上海
0
Xylophone
dsa

1周前来自广东
0
- prediction
  回复
  Xylophone
  PPPPPPPPPPPPPPP
  
  1周前来自浙江
  0
Always 西弗勒斯·斯内普
嗯，对我很有帮助

1周前来自新疆
0
- Xylophone
  回复
  Always 西弗勒斯·斯内普
  dsa
  
  1周前来自广东
  0
古希腊掌管AC和WA的神
您咋这强

1周前来自上海
0
yxdl1
dsa

1周前来自浙江
0
prediction
区。

1周前来自浙江
0

全部评论 6

热门讨论