首先表示对C++读入读出问题复杂程度的敬畏,看了好多没讲明白的,本题用cin竟然过不了评测,搞scanf的读入搞了好久....

本题确实是一道经典的并查集题型,不多讲,拿来练练手用的(其中经历很惨)

用pre[i]表示i到其父节点f[i]之间排几个(父节点算1个)

f[i]表示i的父节点

num[i]表示i的队伍中一共有多少人

大致即 利用父节点与该点距离进行迭代的过程,即pre[x]=pre[x]+pre[f[x]]; 然后每次调整队伍时只要将父节点的位置搞清楚了,其他点都可以根据与父节点关系计算出来

/*看来对于c++这门语言见解不够,或者说c++确实不好用*/

#include
    
     #include
     
      #include
      
       int f[30000],pre[30000],num[30000];using namespace std;int find(int x){    if (f[x]==x) return(x);    find(f[x]);    pre[x]+=pre[f[x]];    f[x]=f[f[x]];    return(f[x]);}int main(){    int n,i,j,k,a,b,fa,fb;    char c;    cin>>n;    for(k=1;k<=30000;k++){        f[k]=k;        num[k]=1;    }    for(k=1;k<=n;k++){        while (getchar()!='\n');//读入问题至今觉得c++的cin和scanf都相当不好用,可能有的作用不知道,但是没找到真正讲得明白其原理的文章;  只能表示pascal的read,readln的强大        scanf("%c",&c);        scanf("%d%d",&a,&b);        fa=find(a);fb=find(b);        if(c=='M'){            f[fa]=fb;            pre[fa]=num[fb];            num[fb]+=num[fa];        }        if(c=='C'){            if(fa==fb){                printf("%d\n",((int)abs(pre[a]-pre[b]))-1);//很奇怪的地方,若abs不用int竟然abs返回值变成0,不知为什么?            }else printf("-1\n");        }    }    return 0;}