花了2h总算把边带权并查集整明白了qaq

1.边带权并查集的用途

众所周知，并查集擅长维护与可传递关系有关的信息。然而我们有时会发现并查集所维护的信息不够用，这时“边带权并查集”就应运而生了。

2.例题与思路

这里通过例题洛谷P1196 [NOI2002] 银河英雄传说来介绍边带权并查集的思想。题面请点击链接查看。

2.1.暴力

拿到这道题我的第一想法就是用链表模拟。对于两艘在同一列的战舰，只需知道它们到队首的距离（设距离分别为 \(dis_1\) 和 \(dis_2\)）就可以知道它们之间的距离（为 \(|dis_1-dis_2|+1\)）。对于每艘战舰，记录它前面的战舰是哪一艘，查询时通过暴力往前跳来查询 \(dis_1\) 和 \(dis_2\)，合并时暴力合并。这样显然会超时，于是我们考虑优化。

2.2.优化

可以考虑使用路径压缩的方式进行优化。对于这样一个链表:

它等价于：

同时这样查询时要跳的步数就少很多。这其实就是路径压缩。

同时我们还需要记录每一列的战舰数，在合并时只需要：

就可以了。

单次操作时间复杂度和并查集一模一样，是 \(\Theta(\alpha(n))\) 的，非常高效。

2.3.Code

废话少说，放码过来！

#include <bits/stdc++.h>

using namespace std;

#define MAXN 30000

int t,fa[MAXN+5],dis[MAXN+5]/*到父亲战舰之间隔了多少战舰*/,siz[MAXN+5]/*每一列的战舰数*/;

int get(int x){//查询

    if(fa[x]==x){

        return x;

    }else{

        int res=get(fa[x]);

        dis[x]+=dis[fa[x]];//路径压缩

        fa[x]=res;

        return res;

    }

}

int main(){

    ios::sync_with_stdio(false);

    for(int i=1;i<=MAXN;i++){

        fa[i]=i;

        siz[i]=1;

    }

    cin>>t;

    while(t--){

        string op;cin>>op;

        if(op=="M"){//合并

            int i,j;cin>>i>>j;

            i=get(i);j=get(j);

            dis[i]+=siz[j];

            fa[i]=j;

            siz[j]+=siz[i];

            siz[i]=0;

        }else{

            int i,j;cin>>i>>j;

            if(get(i)!=get(j)){

                cout<<-1<<endl;

            }else{

                cout<<abs(dis[i]-dis[j])-1<<endl;

            }

        }

    }

    return 0;

}

据说还有一个扩展域并查集，回头博主再了解一下，现在博主要去恰饭了

巴特西

边带权并查集学习笔记 & 洛谷P1196 [NOI2002] 银河英雄传说题解

1.边带权并查集的用途

2.例题与思路

2.1.暴力

2.2.优化

2.3.Code

最新文章

热门文章

巴特西

边带权并查集 学习笔记 & 洛谷P1196 [NOI2002] 银河英雄传说 题解

1.边带权并查集的用途

2.例题与思路

2.1.暴力

2.2.优化

2.3.Code

最新文章

热门文章

边带权并查集学习笔记 & 洛谷P1196 [NOI2002] 银河英雄传说题解