本文主要是介绍MT3052 史莱姆融合（并查集），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
思路：刚开始只觉得不知道该怎样记录这些整数之间左右数据，并没有想到并查集，后来看到提示，但是也没想出该怎样在并查集之中记录左右数据。
后来看了视频后才知道，可以使用next指针来记录整数的前后顺序，然后用另一个指针来记录每个集合的最右（用并查集中原先的pre指针来记录最左），这样在合并的时候就可以很容易地修改每个集合的最左和最右。
代码：
#include<iostream>
#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;const int MAXN=1e6+2;#define LL(x) (x<<1)
#define RR(x) (x<<1|1)int nxt[MAXN],pre[MAXN],ri[MAXN];
int n;void init(){for(int i=1;i<=n;++i){pre[i]=i;ri[i]=i;nxt[i]=-1;}
}int find(int x){if(x!=pre[x])pre[x]=find(pre[x]);return pre[x];
}void join(int x,int y){int fx=find(x),fy=find(y);if(fx!=fy){nxt[ri[fx]]=fy;pre[fy]=fx;ri[fx]=ri[fy];}
}int main() {scanf("%d",&n);init();int x,y;for(int i=1;i<n;++i){scanf("%d %d",&x,&y);join(x,y);}int st=find(1);printf("%d ",st);while(nxt[st]!=-1){printf("%d ",nxt[st]);st=nxt[st];}return 0;
}
这篇关于MT3052 史莱姆融合（并查集）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
