分析：
类似于带权并查集，又由于更新的时候是从根开始叠加，所以pre[i] 为前面含有的战舰数，每次更新pre[i]
再用一个sum数组保存根节点后面的子节点数目，每次合并时将 pre[尾部舰队根节点的] 设为 sum[被接的舰队的根节点]
#include <cstdio> #include <cstring> #include <iostream> #include <algorithm> #include <cmath> using namespace std; #define maxn 30000+5 int fa[maxn]; int sum[maxn]; int pre[maxn]; int find(int x) { if(x == fa[x])return x; int f = fa[x]; fa[x] = find(fa[x]); pre[x] += pre[f]; return fa[x]; } void init() { for(int i = 0 ; i < maxn ; ++i){ fa[i] = i; sum[i] = 1; } } int main() { init(); int T,a,b; char c[3]; cin >> T; while(T--) { scanf("%s %d %d",&c,&a,&b); int x = find(a); int y = find(b); if(c[0] == 'M'){ fa[x] = y; pre[x] = sum[y]; sum[y] += sum[x]; } else { if( x == y ) printf("%d\n",abs(pre[b] - pre[a])-1); else printf("-1\n"); } } }今天的文章 1540 银河英雄传说分享到此就结束了，感谢您的阅读。
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
如需转载请保留出处：https://bianchenghao.cn/bian-cheng-ji-chu/86330.html