【蓝桥杯-带权并查集】接龙

玩一种接龙的游戏，蒜头君有 $30000$张卡片分别放在 $30000$ 列，每列依次编号为 $1,2,...,30000$。同时，蒜头君也把每张卡片依次编号为 $1,2,...,30000$。

游戏开始，蒜头君让让第 $i$ 张卡片处于第 $i(i=1,2,...,30000)$ 列。然后蒜头君会发出多次指令，每次调动指令 $M$ $i$ $j$ 会将第 $i$ 张卡片所在的队列的所有卡片，作为一个整体（头在前尾在后）接至第 $j$ 张卡片所在的队列的尾部。

蒜头君还会查看当前的情况，发出 $C$ $i$ $j$ 的指令，即询问电脑，第 $i$ 张卡片与第 $j$ 张卡片当前是否在同一个队列中，如果在同一列中，那么它们之间一共有多少张卡片。

#include<iostream> #include<bits/stdc++.h> using namespace std; int father[30010]; int dist[30010]; int size[30010]; int get(int a) { if(father[a]==a) return a; int y=father[a]; father[a]=get(y); dist[a]+=dist[y]; return father[a]; } void merge(int aa,int bb) { int a=get(aa); int b=get(bb); if(a!=b) { father[a]=b; dist[a]=size[b]; size[b]+=size[a]; } } int main() { memset(dist,0,sizeof(dist)); for(int i=0;i<30010;i++) { father[i]=i; size[i]=1; } int T; cin>>T; char MORC; int a,b; while(T--) { cin>>MORC>>a>>b; if(MORC=='M') merge(a,b); else if(MORC=='C') { if(get(a)==get(b)) cout<<abs(dist[a]-dist[b])-1<<endl; //求的是“二者之间”还有多少个，所以长度差值还要-1 else cout<<"-1"<<endl; } } return 0; }

做法就是典型的带权并查集（路径压缩），注意两个关键函数get和merge。get里面是一层层的路径压缩来把权值更新了，merge就是把头接到尾去，大家连在一起（同一个根）。

这道题刚开始我在想要不要用vector的，但是发现它是根据卡片的编号来合并的（合并该卡片所在列），并不是通过列的序号来合并，所以应该是用并查集的。而且并查集也很好检验两个编号是不是在同一列——看根相不相同即可。然后看长度，也是可以直接看带权并查集的权值。