博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
并查集 POJ 1988
阅读量:5060 次
发布时间:2019-06-12

本文共 1008 字,大约阅读时间需要 3 分钟。

#include 
#define N 30010int pa[N]; //parentint siz_tree[N]; //size of treeint d[N]; //dist between node and rootint Find(int x){ if(pa[x] == x) return x; int t = pa[x]; pa[x] = Find(pa[x]); d[x] += d[t]; return pa[x];}void Union(int x, int y){ x = Find(x), y = Find(y); pa[x] = y; d[x] += siz_tree[y]; siz_tree[y] += siz_tree[x]; siz_tree[x] = 0;}int main(){ int p; while(~scanf("%d", &p)) { for(int i = 0; i < N; i++) pa[i] = i, siz_tree[i] = 1, d[i] = 0; char c; int x, y; for(int i = 0; i < p; i++) { while(1) { c = getchar(); if(c == 'M' || c == 'C') break; } if(c == 'M') { scanf("%d%d", &x, &y); Union(x, y); } else { scanf("%d", &x); Find(x); printf("%d\n", d[x]); } } } return 0;}

  

转载于:https://www.cnblogs.com/sunus/p/4395129.html

你可能感兴趣的文章
MVC系列博客之排球计分(三)模型类的实现
查看>>
npm安装
查看>>
阅读笔记02
查看>>
2019年春季学期第二周作业
查看>>
2014北邮计算机考研复试上机题解(上午+下午)
查看>>
mySQL 教程 第7章 存储过程和函数
查看>>
OGG同步Oracle到Kafka(Kafka Connect Handler)
查看>>
算法笔记_056:蓝桥杯练习 未名湖边的烦恼(Java)
查看>>
idea的maven项目无法引入junit
查看>>
jquery实现限制textarea输入字数
查看>>
thinkphp5 csv格式导入导出(多数据处理)
查看>>
页面置换算法-LRU(Least Recently Used)c++实现
查看>>
如何获取Android系统时间是24小时制还是12小时制
查看>>
fur168.com 改成5917电影
查看>>
PHP上传RAR压缩包并解压目录
查看>>
codeforces global round 1题解搬运
查看>>
python os模块
查看>>
Codeforces 719B Anatoly and Cockroaches
查看>>
jenkins常用插件汇总
查看>>
c# 泛型+反射
查看>>