题目描述
有一个划分为N列的星际战场，各列依次编号为1,2,…,N。
有N艘战舰，也依次编号为1,2,…,N,其中第i号战舰处于第i列。
有T条指令，每条指令格式为以下两种之一：
1、M i j，表示让第i号战舰所在列的全部战舰保持原有顺序，接在第j号战舰所在列的尾部。
2、C i j，表示询问第i号战舰与第j号战舰当前是否处于同一列中，如果在同一列中，它们之间间隔了多少艘战舰。
现在需要你编写一个程序，处理一系列的指令。
输入格式
第一行包含整数T，表示共有T条指令。
接下来T行，每行一个指令，指令有两种形式：M i j或C i j。
其中M和C为大写字母表示指令类型，i和j为整数，表示指令涉及的战舰编号。
输出格式
你的程序应当依次对输入的每一条指令进行分析和处理：
如果是M i j形式，则表示舰队排列发生了变化，你的程序要注意到这一点，但是不要输出任何信息；
如果是C i j形式，你的程序要输出一行，仅包含一个整数，表示在同一列上，第i号战舰与第j号战舰之间布置的战舰数目，如果第i号战舰与第j号战舰当前不在同一列上，则输出-1。
样例
样例输入
复制4 M 2 3 C 1 2 M 2 4 C 4 2
样例输出
复制-1 1
数据范围与提示
N≤30000,T≤
_____________________________________________________________________________
写作不易，点个赞呗!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
_____________________________________________________________________________
#include<bits/stdc++.h> using namespace std; int a[30005],b[30005],c[30005]; int m,ans; char n; void Un(int x){ for(int i=1;i<=x;i++)a[i]=i,c[i]=1; } int Unfind(int x){ if(a[x]==x)return x; int pa=a[x]; a[x]=Unfind(a[x]); b[x]+=b[pa]; return a[x]; } void Uns(int x,int y){ int q=Unfind(x),p=Unfind(y); if(q==p)return; a[q]=p,b[q]+=c[p],c[p]+=c[q]; } int main(){ ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); Un(30005); cin>>m; for(int x,y,i=1;i<=m;i++){ cin>>n>>x>>y; if(n=='M'){ Uns(x,y); }else{ if(Unfind(x)!=Unfind(y))cout<<"-1\n"; else{ cout<<abs(b[x]-b[y])-1<<"\n"; } } } }
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
如需转载请保留出处：https://bianchenghao.cn/bian-cheng-ji-chu/86363.html