POJ 1988 带偏移量的并查集
2024-08-28 04:02:35
题意:
思路:
数据范围很大 貌似只能用并查集了……
//By SiriusRen
#include <cstdio>
using namespace std;
int p,f[33333],d[33333],xx,yy,s[33333];
int find(int x){
if(x==f[x])return x;
int fx=find(f[x]);
d[x]+=d[f[x]];
return f[x]=fx;
}
int main(){
scanf("%d",&p);
for(int i=1;i<=30000;i++)f[i]=i,s[i]=1;
for(int i=1;i<=p;i++){
st:char op=getchar();
if(op=='M'){
scanf("%d%d",&xx,&yy);
int fx=find(xx),fy=find(yy);
f[fx]=fy,d[fx]+=s[fy],s[fy]+=s[fx];
}
else if(op=='C'){
scanf("%d",&xx),find(xx);
printf("%d\n",d[xx]);
}
else goto st;
}
}
最新文章
- Basic Tutorials of Redis(1) - Install And Configure Redis
- 深入java集合学习1-集合框架浅析
- Oozie_示例
- Html标签的语义化
- 常见的JavaScript函数
- 将已有项目提交到github/从github上pull到本地
- Object.observe
- 洛谷P2015 二叉苹果树
- nade.js(一)进程管理
- 《Intel汇编第5版》 汇编减法程序
- 用C#实现微信“跳一跳”小游戏的自动跳跃助手
- Python之旅本地环境搭建
- unity集成openinstall流程
- [Swift]LeetCode919. 完全二叉树插入器 | Complete Binary Tree Inserter
- 2019-04-15 Python之利用matplotlib和numpy的简单绘图
- ldconfig 的简单用法
- 基于AT89C51单片机烟雾传感器
- OpenGL和D3D11中的深度模版测试
- boost::bind 学习
- 论文分享NO.2(by_xiaojian)
热门文章
- SharePoint UserProfileService 接口列表 注解
- TabLayout中Indicator的样式修改
- PostgreSQL Replication之第七章 理解Linux高可用(6)
- PostgreSQL Replication之第四章 设置异步复制(8)
- asp.net导出execl和图片
- Spring项目的配置文件们(web.xml context servlet springmvc)
- UI Framework-1: views Windowing
- BZOJ 3674: 可持久化并查集模板
- P2420 让我们异或吧(树链剖分)
- XWIKI的搭建