我们可以用并查集维护一些东西，考虑到并查集的根节点一定是某一列的第一个值，那么我们可以维护一个sum数组，用来记录i到i祖先的战舰数，同时需要维护一个num数组，num[i]表示第i列的战舰总数
#include<cstdio> #include<cstring> #include<algorithm> using namespace std; #define maxn 30005 int sum[maxn],father[maxn],num[maxn]; int T; int getfather(int x) { int temp=father[x]; if (x!=father[x]) father[x]=getfather(father[x]); sum[x]+=sum[temp]-1; return father[x]; } int main() { scanf("%d",&T); for (int i=1;i<=30000;i++) { father[i]=i; sum[i]=num[i]=1; } while (T--) { char s[5];int x,y; scanf("%s%d%d",s,&x,&y); int fx=getfather(x); int fy=getfather(y); if (s[0]=='M') { father[fx]=fy; sum[fx]+=num[fy]; num[fy]+=num[fx]; } else { if (fx!=fy) printf("-1\n"); else printf("%d\n",abs(sum[x]-sum[y])-1); } } return 0; }
