首页 > 其他分享 >poj-1988

poj-1988

时间:2023-05-23 16:00:50浏览次数:39  
标签:count cube parent 1988 broot poj 集合 UF


//564K	282MS	C++
#include <cstdio>
#include <cstring>
#include <iostream>

using namespace std;

struct UF_Node{
	int up;
	int count;
	int parent;
};

typedef struct UF_Node UF_Node;

UF_Node UF_Array[30001];

void creat(){
	int c;
	for(c = 0; c<=30000; c++){
		UF_Array[c].count = 1;
		UF_Array[c].parent = c;
		UF_Array[c].up = 0;
	}
}

int UF_find(int x) {
	int xParent = UF_Array[x].parent;

	if (xParent != x) {
		UF_Array[x].parent = UF_find(xParent);
		UF_Array[x].up += UF_Array[xParent].up; 
	} 
	return UF_Array[x].parent;
}

// a set top of b set
void UF_Union(int a, int b) {
	int aroot = UF_find(a);
	int broot = UF_find(b);

	UF_Array[broot].up = UF_Array[aroot].count;	
	UF_Array[aroot].count += UF_Array[broot].count;
	UF_Array[broot].parent = aroot;
}

int main(){
	creat();
	int n,a,b;
	char s;
	cin>>n;
	while(n--){
		cin>>s;
		if(s == 'M'){
			scanf("%d %d",&a,&b);
			UF_Union(a,b);
		}
		else if(s == 'C'){
			scanf("%d",&a);
			b = UF_find(a);
			printf("%d\n",UF_Array[b].count - UF_Array[a].up - 1);
		}
	}
	return 0;
}


非常好的并查集的题, 看到这道题的时候,就感觉似乎可以跟集合 并查集扯上关系,但是因为自己的固定思维,觉得并查集只是用来判断是否一个集合之类的问题,这道题要求的是计数,觉得扯不上,后来搜了下,才发现并查集在加入一些扩展之后,也可以解这样的题,不由感叹数据结构真是博大精深,扩展一下就是一个新天地。

其实就是扩展了两个数据项: 一个是up 表示 此cube所属的集合(也就是stack)上面一共有多少个cube, 第二个是count,这个值只有在cube是stack的第一个元素(也就是集合的root)的时候才有效,代表着此集合(stack)所有的cube的数量,那么当要求某个cube X下面有多少个cube时,

在知道了此cube所属的stack(集合)有多少个cube: count,以及此cube上面有多少个cube: up, 此cube所属stack(集合)在X下面的cube数量就是 count - up - 1.

一些关键的操作就是:

<1> 在UF_Union(a, b), 即将a所属的stack加到 b所属的stack上时,除了更新常规的parent外,还要更新 aroot的count值,因为broot集合并入了aroot,那么aroot代表的集合的count就要加上 broot集合的数量, broot不用变化,因为broot已经不是 集合的root, 同时,因为broot上面有了cube,所以要将broot的up从 0 更新为 aroot集合的count,因为aroot集合的所有cube都在broot上面。

<2> 在UF_Find(a), 除了将a的parent更新为 aroot外,还有很关键的一点: a 的 up 要加上 其 parent(注意,这个parent是没有递归UF_find更新其parent之前的parent,可以理解为在一次合并以后, a的parent还没有更新,仍然指向原来集合的那个 parent,也就是 root), 因为 a原来的parent, 其up一定是0(因为在stack的最上面,因此上面没有cube), 那么在合并以后,其up就被更新aroot集合的count,这样,broot所属的stack,每个cube上面都多了 aroot的count,因此,在UF_find递归处理时,进行此操作,就等于将broot的每个cube都做了 +count的处理(递归一直是很巧妙的结构).


标签:count,cube,parent,1988,broot,poj,集合,UF
From: https://blog.51cto.com/u_9420214/6333001

相关文章

  • poj-1693
    //136K 0MS C++#include<cstdio>#include<cstring>structLine{ intbx,ex; intby,ey;};typedefstructLineLine;LinehLine[110];LinevLine[110];intcaseNum;intLineNum;boolinsect(Line&vline,Line&hline){ //pr......
  • POJ1737 Connected Graph ( n点无向连通图计数
    题意说明:求\(n\)个点的无向连通图个数据说已经非常典了,但是我太菜了不会组合数学,最近补档时看到这道题,决定记录下来理理思路......
  • POJ--1163 The Triangle(DP)
    记录10:432023-5-15http://poj.org/problem?id=1163reference:《挑战程序设计竞赛(第2版)》第二章练习题索引p135DescriptionFigure1showsanumbertriangle.Writeaprogramthatcalculatesthehighestsumofnumberspassedonaroutethatstartsatthetopa......
  • 实验六-Salt本地pojie实验
    【实验目的】了解Salt型密码的加密机制,学会使用本地密码pojie工具来pojieSalt型密码,了解pojie密码原理。【知识点】Salt,密码pojie【实验原理】1.Salt概念在密码保护技术中,salt是用来修改口令散列的随机数据串。可将salt加入散列,即使系统的另一用户也选用了同一口令,也可通过唯......
  • POJ 动态规划题目列表
    声明:1.这份列表当然不是我原创的,从文库里下载了一份,放到这里便于自己浏览和查找题目。※最近更新:Poj斜率优化题目1180,2018,3709列表一:经典题目题号:容易:1018, 1050, 1083, 1088, 1125, 1143, 1157, 1163, 1178, 1179, 1189, 1191,1208, 1276, 1322, 1414, 1456, 1458......
  • poj018(2)
    再贴一版poj1018,其实与之前的那一版差不多,只是去掉了注释,这样可能看起来会舒服一点packagecom.njupt.acm;importjava.io.BufferedReader;importjava.io.InputStreamReader;importjava.util.Arrays;importjava.util.Scanner;publicclassTestPOJ1018{pu......
  • poj1018(1)
    其实这道题我也没有完全的弄明白,糊里糊涂就ac了 大致题意:某公司要建立一套通信系统,该通信系统需要n种设备,而每种设备分别可以有m1、m2、m3、...、mn个厂家提供生产,而每个厂家生产的同种设备都会存在两个方面的差别:带宽bandwidths和价格prices。现在每种设备都各需要1个,考虑......
  • poj1013
    大致题意:有一打(12枚)硬币,其中有且仅有1枚假币,11枚真币用A~L作为各个硬币的代号假币可能比真币略轻,也可能略重现在利用天枰,根据Input输入的3次称量,找出假币,并输出假币是轻还是重。 解题思路:模拟法要考虑的情况较繁琐,可利用简单的逻辑推理进行解题。  注意Input一行代......
  • POJ2739 Sum of Consecutive Prime Numbers&&Acwing4938 连续质数之和
    方法:单调队列为什么是单调队列?因为这里让我们求连续的质数和,我们可以利用欧拉筛来维护质数,再利用单调队列来维护连续的质数。代码(POJ不支持C++11差评):#include<cstdlib>#include<cstring>#include<cstdio>#include<cctype>namespaceFastIo{ #definegcgetchar() #d......
  • color a tree poj2054
    coloratree(贪心)题目描述可以得到一个确定性的结论,最大值的结点一定是在父节点染色后立即染色。但是此时依结论不好在复杂的情况正推,先考虑简单情况:假如有权值x,y,z三个点,已知x,y一定一起染色,则有两种可能方案:先x,y,再z,代价为X=x+2y+3z先z,再x,y,代价为Y=2x+3y+zX-Y=2z-......