题目传送门

带权并查集问题。

用fr[x]数组记录x战舰前(不包括自己)有几艘战舰,beh[x]数组记录x战舰后(包括自己)有几艘战舰。

并查集即可。

code

#include <cstdio>
#include <cmath>
#include <iostream>
using namespace std;
int fa[],T,fr[],beh[];
int getf(int x){//并查集
if(x==fa[x])return x;
int k=getf(fa[x]);
fr[x]+=fr[fa[x]];
fa[x]=k;
return fa[x];
}
void unino(int x,int y){
int fx=getf(x),fy=getf(y);
fa[fx]=fy;
fr[fx]=beh[fy];//这里之所以能这样做,是因为并查集时会自动更新。
beh[fy]+=beh[fx];
}
int check(int x,int y){
int fx=getf(x),fy=getf(y);
if(fx==fy)return abs(fr[x]-fr[y])-;
else return -;
}
int main(){
scanf("%d",&T);
for(int i=;i<=;i++)fa[i]=i,beh[i]=;
while(T--){
char c;cin>>c;
int x,y;scanf("%d%d",&x,&y);
if(c=='M')unino(x,y);
else printf("%d\n",check(x,y));
}
}

最新文章

  1. 前端学HTTP之重定向和负载均衡
  2. jQuery动态增删改查表格信息,可左键/右键提示
  3. 【原】dangerouslySetInnerHTML, 让React正常显示你的html代码
  4. Python中判断是否为闰年,求输入日期是该年第几天
  5. winform小程序---猜拳小游戏
  6. TCP三次握手及四次挥手详细图解
  7. CoreOS实践(2)—在coreos上安装Kubernetes
  8. 「ubuntu」通过无线网络安装Ubuntu Server,启动系统后如何连接无线网络
  9. asp.net日志跟踪方法
  10. WordPress插件:幻灯片Meta Slider
  11. 从一个乘法来分析C语言
  12. 关于Git的工作区域和对应的文件状态.
  13. 数据库字段出现科学计数法e+的情况分析
  14. 有关UNICODE、ANSI字符集和相关字符串操作
  15. TCP之超时和重传
  16. lesson - 1 笔记 网络连接 /putty 密钥登陆
  17. css样式清零及常用类
  18. 非负矩阵分解NMF
  19. windows 重写调试输出
  20. PRTG参考价格

热门文章

  1. Android SharedPreferences基本用法
  2. js中匿名函数
  3. 匿名委托与Lambda表达式
  4. hdu 6107--Typesetting(倍增)
  5. MySQL使用聚合函数查询
  6. Html5笔记之第四天
  7. 用xml画水平虚线和竖直虚线.md
  8. mysql 插入字段 字符串
  9. jmeter后置处理器 JSON Extractor取多个变量值
  10. Spring-MVC开发步骤(入门配置)