E. Merging Towers（并查集+启发式合并）

清疚 2023-02-27 05:48 68阅读 0赞

题意就是汉诺塔的玩法，加上合并塔后问你把他们排为有序需要多少步（具体讲好麻烦，就这么糊弄过去吧！）

错误写法：每个盘有个belong说明在哪个塔 每个塔用并查集维护根节点，链表写法：每个盘连着下一个，如果某个盘和下一个盘find（be\[x\]）相等则压缩路径，每合并一次塔跑一遍链表（T在这了）

比如m拉满每个塔一个盘 时间复杂度就是n^2了

启发式合并写法

并查集维护根节点，维护每次的操作数sum，合并塔时，遍历size小的塔的所有数据然后看他的-1和+1和他是不是一个根节点，是的话sum--

时间复杂度证明：极限情况m拉满每个塔数目为1 每次合并两个塔 共有logm层，每层时间为m

总时间为mlogm

（也是今天才知道这就是启发式合并）

其实我第一份代码两边都跑了，结果删掉了启发式合并部分，留下了链表，hai

AC代码

#include<bits/stdc++.h>
    using namespace std;
    typedef long long ll;
    const int N=2e5+6;
    int be[N];
    int f[N];
    vector<int>son[N];
    int fid(int x)
    {
        if(x==f[x]) return f[x];
        f[x]=fid(f[x]);
        return f[x];
    }
    int main()
    {
    
        int n,m;
        cin>>n>>m;
        for(int i=1;i<=n;i++)
        {
            f[i]=i;
            int x;
           scanf("%d",&x);
            be[i]=x;
            son[x].push_back(i);
        }
            int d=1;
            int sum=n-1;
            for(int i=2;i<=n;i++) if(be[i]==be[i-1]) sum--;
        vector<int>ans;
        ans.push_back(sum);
        cout<<sum<<endl;
        m--;
        while(m--)
        {
            int a1,a2;
           scanf("%d%d",&a1,&a2);
            int fx=fid(a1);
            int fy=fid(a2);
            if(son[fx].size()<son[fy].size()) swap(fx,fy);
    
    //cout<<fx<<' '<<fy<<endl;
        for(int i=0;i<son[fy].size();i++)
        {
            int d=son[fy][i];
            if(fid(be[d-1])==fx) sum--;
            if(fid(be[d+1])==fx) sum--;
            son[fx].push_back(d);
        }
        f[fy]=fid(fx);
        cout<<sum<<endl;
        }
    
    }