并查集——以nuist OJ P1648炼丹术为例
并查集
定义:并查集是一种树形的数据结构,用于处理一些不相交集合的合并及查询问题
主要构成:
并查集主要由一个整型数组pre[]和两个函数find()、join()构成。
数组pre[]记录了每个点的前驱结点是谁,函数find(x)用于查找指定结点x属于哪个集合,函数join(x,y)用于合并两个结点x和y。
作用:
并查集的主要作用是求联动分支数。
代表元:
用集合中的某个元素来代表这个集合,则该元素称为此集合的代表元
find()函数的定义与实现:
int find(int x){
while(pre[x]!=x) //如果代表元不是自己
x = pre[x]; //x继续向上找其上级,直到找到代表元为止
return x;
}
join()函数的定义与实现:
void join(int x,int y){
int fx = find(x),fy=find(y);
if(fx!=fy)
pre[fx] = fy;
}
路径压缩算法:将x到根节点路径上的所有点的上级都设为根节点
//递归实现
int find(int x){
if(pre[x] == x) return x;
return pre[x] = find(pre[x]);
}
//循环实现
int find(int x) {
while(x!=pre[x])x=pre[x]=pre[pre[x]];
return x;
}
总结:
1、用集合中的某个元素来代表这个集合,则该元素称为此集合的代表元; 2 、一个集合内的所有元素组织成以代表元为根的树形结构; 3 、对于每一个元素 x,pre[x] 存放 x 在树形结构中的父亲节点(如果 x 是根节点,则令pre[x] = x); 4 、对于查找操作,假设需要确定 x 所在的的集合,也就是确定集合的代表元。可以沿着pre[x]不断在树形结构中向上移动,直到到达根节点。 因此,基于这样的特性,并查集的主要用途有以下两点: 1、维护无向图的连通性(判断两个点是否在同一连通块内,或增加一条边后是否会产生环); 2、用在求解最小生成树的Kruskal算法里。
//代码汇总
const int N = 1005 //指定并查集所能包含的元素个数
int pre[N];
int rank[N];
void init(int n){
for(int i=0;i<n;i++){
pre[i] = i;//每个节点的上一级都是自己
rank[i] = 1;
}
}
int find(int x){
if(pre[x] == x) return x;
return find(pre[x]);
}
int find(int x){
if(pre[x] == x) return x;
return pre[x] = find(pre[x]);
}
//判断两个结点是否连通
bool isSame(int x,int y){
return find(x) == find(y);
}
bool join(int x,int y){
x = find(x);
y = find(y);
if(x == y) return false;
if(rank[x] >rank[y]) pre[y] = x;
else{
if(rank[x] == rank[y]) rank[y]++;
pre[x] = y;
}
return true;
}
例:炼丹术
题目描述
三水最近在学习炼丹术。但是众所周知炼丹术是一门危险的学科,需要大量的调参才能保证安全。好在三水在洗衣机里面找到了一张失传已久的图纸,里面记录了若干种材料的药性。这张图纸上记录了 n种不同的药材,对于每种药材,都需要恰好一种药材来使其稳定 (这种药材可能是其自身,即这种药材本身就很稳定)。三水想知道,通过这张图纸,可以得到多少种不同的稳定的丹方。保证每种药材只会作为稳定剂出现一次。
我们认为一个丹方是从 n种药材中选择若干种 (不为 0 ),两个丹方被认为是不同的当且仅当存在一种药材在其中一个丹方中且不在另一个中。我们称一个丹方是稳定的,当且仅当所有出现在丹方中的药材的稳定剂也在药材中。
因为输出结果可能很大,所以答案对 998244353 取模。
输入描述
第一行一个数字 nn , 表示有 n (1\leqslant n\leqslant 10^6)n(1⩽n⩽106) 种不同的药材。 接下来一行 n个数字,第 i数字 a_i (1\leqslant a_i\leqslant n)a**i(1⩽a**i⩽n) 表示药材 ii 的稳定剂是 a_ia**i,保证输入是 11 到 nn 的一个全排列。
输出描述
一个整数 nn ,表示答案对 998244353 取模的结果。
样例输入
6 2 3 4 5 6 1
样例输出
1
思路:
AC代码
#include<cstdio>
#include<iostream>
const int MAXN=1000005;
const int INF=0x3f3f3f3f;
const int mod=998244353;
using namespace std;
int pre[MAXN], a[MAXN];
int find(int x) {
while(x!=pre[x])x=pre[x]=pre[pre[x]];
return x;
}
int pow(int n) {
int ans=1,base=2;
for(int i=1;i<=n;++i) {
ans=(ans*base)%mod;
}
return ans;
}
int main() {
int n;
scanf("%d",&n);
for(int i=1;i<=n;++i) {
scanf("%d",&a[i]);
pre[i]=i;//初始化查数组
}
for(int i=1;i<=n;++i) {
int u=find(i), v=find(a[i]);//通过前缀数组更新并查集,查询过程中进行路径压缩
if(u!=v)pre[u]=v; //合并相关联集合
}
int cnt=0;
for(int i=1;i<=n;++i) { //记录不同集合个数
if(pre[i]==i) cnt++;
}
printf("%d",pow(cnt)-1);
return 0;
}
最新文章
- MongoDB系列(一):简介及安装
- Android Programing 学习笔记(一)
- CentOS 7 上编译安装MySQL 5.6.23
- 概念学习(Concept Learning)
- when compile /home/wangxiao/NVIDIA-CUDA-7.5 SAMPLES, it warning: gcc version larger than 4.9 not supported, so: old verson of gcc and g++ are needed
- Linux常用命令英文全称与中文解释Linux系统
- MemSQL start[c]up Round 2 - online version(DP)
- [记录]使用Gitblit 在windows 上安装Git Server
- Javaweb之Jsp
- u盘安装原版win10系统1703更新
- js excel 列表导出
- 阿里云windows2012+iis8配置https
- kubectl命令自动补全
- terraform 几个方便的工具
- 1.3.6、CDH 搭建Hadoop在安装之前(端口---DistCp使用的端口)
- SQL Server 不同网段IP通过名称访问
- cpython和lua源码阅读
- 使用Eclipse可以启动服务器,却不能访问localhost
- show-overflow-tooltip 宽度设置
- Windows10 下安装配置IIS + MySQL5.7.19 + nginx1.12.1 + php7.1.7
热门文章
- 数据仓库(5)数仓Kimball与Inmon架构的对比
- CSS中宽度与高度
- Emscripten教程之入门指导
- Shiro 安全框架详解二(概念+权限案例实现)
- layui文件上传组件“请求上传接口出现异常”问题解决方案
- 解决vscode开发react项目没有html标签自动补全
- Python入门-程序测试
- mysql_install_db 一次修复密码
- Go xmas2020 学习笔记 06、Control Statements、Declarations &; Types
- MassTransit 入门(一)