接龙(计蒜客)
蒜头君在玩一种接龙的游戏，蒜头君有 3000030000 张卡片分别放在 3000030000 列，每列依次编号为 1,2,...,300001,2,...,30000。同时，蒜头君也把每张卡片依次编号为 1,2,...,300001,2,...,30000。
游戏开始，蒜头君让让第 ii 张卡片处于第 i(i = 1,2,...,30000)i(i=1,2,...,30000) 列。然后蒜头君会发出多次指令，每次调动指令 MM ii jj 会将第 ii 张卡片所在的队列的所有卡片，作为一个整体（头在前尾在后）接至第 jj张卡片所在的队列的尾部。
蒜头君还会查看当前的情况，发出 CC ii jj 的指令，即询问电脑，第 ii 张卡片与第 jj 张卡片当前是否在同一个队列中，如果在同一列中，那么它们之间一共有多少张卡片。
聪明的你能不能编写程序处理蒜头君的指令，以及回答蒜头君的询问呢？
输入格式
第一行有一个整数 TT（1\leq T\leq 5000001≤T≤500000），表示总共有 TT 条指令。
以下有 TT 行，每行有一条指令。指令有两种格式：
MM ii jj：ii 和 jj 是两个整数（1\leq i, j\leq 300001≤i,j≤30000），表示指令涉及的卡片编号。你需要让第 ii 张卡片所在的队列的所有卡片，作为一个整体（头在前尾在后）接至第 jj 张卡片所在的队列的尾部，输入保证第 ii 号卡片与第 jj 号卡片不在同一列。
CC ii jj：ii 和 jj 是两个整数（1\leq i, j\leq 300001≤i,j≤30000），表示指令涉及的卡片编号。该指令是蒜头君的询问指令。
输出格式
如果是蒜头君调动指令，则表示卡片排列发生了变化，你的程序要注意到这一点，但是不要输出任何信息；
如果是蒜头君的询问指令，你的程序要输出一行，仅包含一个整数，表示在同一列上，第 ii 号卡片与第 jj 号卡片之间的卡片数目（不包括第 ii 张卡片和第 jj 张卡片）。如果第 ii 号卡片与第 jj 号卡片当前不在同一个队列种中，则输出 -1?1。
样例输入
4
M 2 3
C 1 2
M 2 4
C 4 2
样例输出
-1
1
【接龙(计蒜客)】
#include
#include
using namespace std;
int father[30050],size[30050],dist[30050],ans[500050];
int T,a,b;
char c;
//int c;
void init(){
for(int i = 1;
i <= 30000;
i ++){
father[i] = i;
size[i] = 1;
dist[i] = 0;
}
}int get(int x){
if(father[x] == x){
return x;
}
int y = father[x];
father[x] = get(y);
dist[x] += dist[y];
return father[x];
}void merge(int x,int y){
int n = get(x);
int m = get(y);
if(n != m){
father[n] = m;
dist[n] = size[m];
size[m] += size[n];
}
}bool same(int x,int y){
return (get(x) == get(y));
}int main(){
int index = 1;
init();
scanf("%d",&T);
for(int i = 1;
i <= T;
i ++){
//scanf("%c%d%d",&c,&a,&b);
cin >> c >> a >> b;
if(c == 'M'){
merge(a,b);
}else{
if(same(a,b)){
get(a);
get(b);
ans[index++] = (dist[b]>dist[a]?(dist[b]-dist[a]):(dist[a]-dist[b]))-1;
}else{
ans[index++] = -1;
}
}
}
for(int i = 1;
i < index;
i ++){
printf("%d\n",ans[i]);
}
return 0;
} 推荐阅读
- 增长黑客的海盗法则
- 成交的种子咖啡冥想
- 生命过客——第10章|生命过客——第10章 初为人母
- Python（pathlib模块）
- 九藏拾遗
- 有人与我谈格局
- 装修公司如何寻找精准客户
- 小程序有哪些低成本获客手段——案例解析
- 卓德外汇苗苗/职业投机客“持续掌握优势”的秘密
- 程序员客栈TOP收入的萌系开发者心得|程序员客栈TOP收入的萌系开发者心得 - 雨晴