POJ 1988 Cube Stacking(并查集+路径压缩)
2024-09-29 21:45:47
题目链接: id=1988">POJ 1988 Cube Stacking
并查集的题目
【题目大意】
有n个元素,開始每一个元素自己 一栈。有两种操作,将含有元素x的栈放在含有y的栈的顶端,合并为一个栈。
另外一种操作是询问含有x元素以下有多少个元素。
用sum数组储存每一个栈中的元素个数。每次合并的时候将sum加到 父亲节点。也就是每一个栈的最底部。
用under数组储存当前节点以下有多少元素。每次合并的时候,就能够将顶端元素的under赋值为父节点也就是栈最底部的sum。
void Union(int x,int y){
int xr = find(x);
int yr = find(y);
if(xr==yr) return;
father[xr]=yr;
under[xr]=sum[yr];
sum[yr]+=sum[xr];
}
在查询的时候,运用递归的思想。从底部往上加under。
int find(int x){
if(x==father[x])
return father[x];
int tmp = find(father[x]);
under[x]+=under[father[x]]; //细致想想
father[x]=tmp;
return tmp;
}
【源码】
#include <iostream> //父亲节点在栈的底部
#include <cstdio>
using namespace std;
const int maxn = 30000+10;
int father[maxn];
int under[maxn];
int sum[maxn];
void init(){
for(int i=0;i<maxn;i++){
father[i]=i;
under[i]=0;
sum[i]=1;
}
}
int find(int x){
if(x==father[x])
return father[x];
int tmp = find(father[x]);
under[x]+=under[father[x]];
father[x]=tmp;
return tmp;
}
void Union(int x,int y){
int xr = find(x);
int yr = find(y);
if(xr==yr) return;
father[xr]=yr;
under[xr]=sum[yr];
sum[yr]+=sum[xr];
}
int main(){
int n;
while(scanf("%d",&n)!=EOF){
char ch;
int a,b;
init();
for(int i=0;i<n;i++){
scanf(" %c",&ch);
if(ch=='M'){
scanf("%d%d",&a,&b);
Union(a,b);
}
else{
scanf("%d",&a);
int x=find(a); //仅仅是用来累加一下under
printf("%d\n",under[a]);
}
}
}
return 0;
}
最新文章
- lua语法备忘录
- node socket onmessage
- hihocoder 1037 数字三角形
- Java学习笔记——动态代理
- white-space norma nowrap强制同一行内显示所有文本文字,让所有文字内容中一排显示不换行
- 关于html控件和服务器控件摁回车后提交按钮的问题
- HDU 2544-最短路(最短路spfa)
- C++待解
- 史上最全CentOS安装教程,图文结合
- Cairo-Dock 系统关机无效
- poj1002总结
- IEnumerable和IEnumerator使用
- angularjs 下滑线滑动
- 最实用的深度学习教程 Practical Deep Learning For Coders (Kaggle 冠军 Jeremy Howard 亲授)
- 数据序列化导读(2)[YAML]
- Centos之常见目录作用介绍
- Oracle PLSQL Demo - 12.定义包体[Define PACKAGE BODY]
- python中的内置函数(一), lambda, filter, map
- apache DOCUMENT_ROOT
- 《软件工程综合实践专题》第三次作业——原型工具Axure RP8 的介绍