- Java锁的逻辑(结合对象头和ObjectMonitor)
- 还在用饼状图?来瞧瞧这些炫酷的百分比可视化新图形(附代码实现)⛵
- 自动注册实体类到EntityFrameworkCore上下文,并适配ABP及ABPVNext
- 基于Sklearn机器学习代码实战
我们在处理问题的时候,可能会遇到一些需要维护每个元素所在的集合的问题,而并查集却恰好完美解决了这个问题.
对于普通的并查集,他支持的操作比较少,只有合并和查询,合并是指把两个集合合并成一个,而查询是询问两个元素是否在同一集合内;对于这两种操作,我们可以用一个数组 \(f\) 来存放当前点所属的集合的代表元素编号,例如, \(f[i]=3\) 表示的就是第 \(i\) 个元素属于编号为 \(3\) 的元素所在的集合,那么你可能会问了,用了这个数组,查询是好办了,我们可以直接写一个 find 函数来查询:
inline void fid(int x){return f[x]==x?x:fid(f[x]);}
//如果当前的父节点是自己就返回自己,反之返回代表元素的集合所在的代表元素编号依次直到f[x]==x;
当然我们在使用的时候发现这个 fid 如果一直往后递归会很费时间,所以我们用可以用以下的代码来优化一下:
inline void fid(int x){return f[x]==x?x:f[x]=fid(f[x]);}
这种优化也叫路径压缩,我个人的理解就是加了个记忆化.
那合并呢,咋搞?
假设我们需要把 \(x\) 和 \(y\) 所属的两个集合合并.
法一:直接暴力把所有的点遍历一遍,把所有的属于 \(y\) 所属的集合的 \(f\) 数组给暴力修改成 \(x\) 所属的集合的代表元素编号。复杂度 \(O(n)\) 。
法二:只修改 \(f[y]\) 的值,让他所属的集合代表元素的编号修改为 \(x\) 所属的集合代表元素的编号,后面在遇到和 \(y\) 原先属于同一集合的元素时再更新。复杂度 \(O(1)\) 。
很显然第一个会 T 飞,第二个复杂度很不错但是如何来实现呢?
我们之前记录的 \(f\) 数组是有大用的,配合我们的 fid 函数使我们可以轻而易举的完成法二,当你把 \(y\) 所属的集合的代表元素编号改为 \(x\) 所属的集合的代表元素编号,这样我们在后面的时候再查到所属集合为 \(y\) 所属的集合的元素时,我们就会因为 fid 函数一步一步递归更新 \(f\) 数组的值来实现法二操作了.
但是当 \(f[y]=k\) 而 \(f[k]=k\) 的时候怎么办,那样不就没法更新了吗?
所以我们在进行修改的时候改的其实并不是把 \(f[y]=f[x]\) ,而是 \(f[fid(y)]=f[fid(x)]\) ,直接从根源合并,这样就可以做到合并操作了.
code:
#include<bits/stdc++.h>
using namespace std;
int n,m,f[100010];
inline int fid(int x)
{
if(f[x]==x)return x;
else return f[x]=fid(f[x]);
}
int main()
{
cin>>n>>m;
for(int i=1;i<=n;i++)
f[i]=i;
for(int i=1;i<=m;i++)
{
int op,x,y;
cin>>op>>x>>y;
if(op==1)
{
int xx=fid(x);
int yy=fid(y);
f[xx]=f[yy];
}
else if(op==2)
{
int xx=fid(x);
int yy=fid(y);
if(xx==yy)
cout<<"Y"<<endl;
else cout<<"N"<<endl;
}
}
return 0;
}
我也不知道是不是叫这个名字,但是是解决 \(n\) 个点有 \(m\) 对关系,把 \(n\) 个节点放入两个集合里,要求每对存在关系的两个节点不能放在同一个集合这类的问题的一个并查集.
结合一道题目来讲一下具体怎么用:
一个人的朋友的朋友是朋友 一个人的敌人的敌人是朋友 。
把一个人 \(i\) 劈成两半,一好 \(i\) 一坏 \(i+n\) ,当一个人 \(j\) 和他是朋友的时候,和好的是同一个集合,合并 \(j\) 和 \(i\) ;如果是敌人,就和坏的是同一集合,合并 \(j\) 和 \(i+n\) , \(j+n\) 和 \(i\) .
最后你就会发现,和 \(i\) 为敌的都和 \(i+n\) 在一个集合里,和 \(i\) 处于不同集合,这样我们也就完成了题目的要求.
如果 \(a\) 和 \(b\) 是敌人,合并 \(n+b\) 和 \(a\) , \(n+a\) 和 \(b\) 。
如果 \(c\) 和 \(a\) 是敌人,合并 \(n+c\) 和 \(a\) , \(n+a\) 和 \(c\) 。
那么 \(b\) 和 \(c\) 就并在一起了 。
code
#include<bits/stdc++.h>
using namespace std;
int n,m,f[15000],bd[15000],ans=0;
int fid(int x)
{
if(f[x]==x)return f[x];
else return f[x]=fid(f[x]);
}
void cun(int x,int y)
{
int xx=fid(x);
int yy=fid(y);
if(xx!=yy)f[yy]=xx;
}
int main()
{
cin>>n>>m;
for(int i=1;i<=n*2;i++)
f[i]=i;
for(int i=1;i<=m;i++)
{
int b,c;
char a;
cin>>a>>b>>c;
if(a=='F')
cun(b,c);
if(a=='E')
{
cun(b+n,c);
cun(c+n,b);
}
}
for(int i=1;i<=n;i++)
{
int t=fid(i);
if(bd[t]==0)
bd[t]=1,ans++;
}
cout<<ans<<endl;
return 0;
}
这个题和上面的有什么区别?
上一个题目里一个人只需要劈两半,因为 A 可以和 B 为敌,B 和 A 为敌.
但是这个不可以,A 可以吃 B,但这样 B 不能吃 A.
所以我们一个人劈三半!A 吃 B,B 吃 C,C 吃 A! 。
在合并的时候,我们就正常每一个集合都合并,对于 A 吃 B 之类的操作,依次标记即可.
code:
#include<bits/stdc++.h>
#define N 10001000
using namespace std;
int n,k,f[N],ans,a,b,c;
inline int fid(int x){return f[x]==x?x:f[x]=fid(f[x]);}
signed main()
{
cin>>n>>k;
for(int i=1;i<=3*n;i++)f[i]=i;
for(int i=1;i<=k;i++)
{
cin>>a>>b>>c;
if(b>n||c>n){ans++;continue;}
if(a==1)
{
if(fid(b+n)==fid(c)||fid(c+n)==fid(b)){ans++;continue;}
f[fid(b)]=fid(c);
f[fid(b+n)]=fid(c+n);
f[fid(b+n+n)]=fid(c+n+n);
}
if(a==2)
{
if(fid(b)==fid(c)||fid(b)==fid(c+n)){ans++;continue;}
f[fid(b+n)]=fid(c);
f[fid(b+n+n)]=fid(c+n);
f[fid(b)]=fid(c+n+n);
}
}
cout<<ans<<endl;
return 0;
}
我记得这东西还叫带权并查集.
这个东西和普通的并查集有什么区别嘞?
他可以查询两个点之间的距离.
然后就没有别的了。。。.
我也不是很明白这个东西是怎么实现的,但是可以讲一下下面的这个题目(以后一定来填坑) 。
这个题目的询问不太一样:询问两个战舰之间的战舰数量.
我们开一个数组 \(f\) 来存放当前战舰到这一列尽头之间的战舰数量,然后用 \(fa\) 来表示当前的点所属的集合的代表元素的编号,其次,我们还需要一个 \(num\) 数组来存放当前集合,也就是这一列的战舰总数.
我们和普通的并查集相比,其实只有两点不同:
一是我们的 fid 函数,在路径 亚索 压缩的时候顺便把 \(f\) 数组也要处理一下,比如说,在路径压缩的时候我们是相当于把这个点接到更新后的点所在列的后面,所以我们要这样改:
inline int fid(int x)
{
if(fa[x]==x)return x;//如果要是相等直接返回
int ff=fid(fa[x]);//更新后的代表元素编号
f[x]+=f[fa[x]];//累加求和
return fa[x]=ff;//返回新的代表元素编号
}
第二就是合并操作的改变,同样我们除了改变 \(fa\) 以外还要修改 \(f\) 数组,所以我们这样合并:
f[xx]+=num[yy];//把xx一列接到yy一列的后面,所以直接加上num[yy]
fa[xx]=yy;//更新fa
num[yy]+=num[xx];//累加战舰数量
num[xx]=0;//清零
其实我觉得带权并查集都可以把集合给相成拍一列,因为这样的话能比较好理解和实现.
code:
#include<bits/stdc++.h>
#define int long long
#define N 1000100
using namespace std;
int n,x,y,num[N],f[N],fa[N];
inline int fid(int x)
{
if(fa[x]==x)return x;//如果要是相等直接返回
int ff=fid(fa[x]);//更新后的代表元素编号
f[x]+=f[fa[x]];//累加求和
return fa[x]=ff;//返回新的代表元素编号
}
signed main()
{
for(int i=1;i<=30000;i++)
fa[i]=i,f[i]=0,num[i]=1;
cin>>n;
while(n--)
{
char c;
cin>>c>>x>>y;
int xx=fid(x);
int yy=fid(y);
if(c=='M')
{
f[xx]+=num[yy];//把xx一列接到yy一列的后面,所以直接加上num[yy]
fa[xx]=yy;//更新fa
num[yy]+=num[xx];//累加战舰数量
num[xx]=0;//清零
}
else
{
if(xx!=yy)cout<<"-1"<<endl;
else cout<<abs(f[x]-f[y])-1<<endl;
}
}
return 0;
}
之前的并查集都弱爆了,这个才是最强并查集.
前置知识:主席树,并查集 。
md没看懂,先咕了 。
最后此篇关于并查集の进阶用法的文章就讲到这里了,如果你想了解更多关于并查集の进阶用法的内容请搜索CFSDN的文章或继续浏览相关文章,希望大家以后支持我的博客! 。
MySQL表的增删改查(进阶) 1. 数据库约束 约束类型 说明 示例 NULL约束 使用NOT NULL指定列不为空 name varchar(20) not null, UNIQUE唯一约束 指定
多线程(进阶) 1. 常见的锁策略 1.1 乐观锁 悲观锁 乐观锁 : 总是假设最好的情况,每次去拿数据的时候都认为别人不会修改数据,但是在对数据提交更新的时候,再去判断这个数据在这个期间是否有别人对
我相信在正确编码的系统中-错误(作为错误或异常)应该是不可能的(DB/memcached服务器故障导致查询失败)。我们的代码不应依赖任何假设才能正常工作,并且应尽可能地证明其正确性。 但是,为了确保我
1. 前言 泛型代码让你能根据你所定义的要求写出可以用于任何类型的灵活的、可复用的函数。你可以编写出可复用、意图表达清晰、抽象的代码。 泛型是 Swift 最强大
一、创建质量配置及关联项目 1.新建一个java代码质量配置 2.为配置添加规则 确认有4条规则了 为项目更换扫描配置 二、创建质量阈关联项目 1.
完整jenkinsfile 、sharelibrary 及jenkins配置见最后 一、gitlab push分支自动匹配 1.添加Generic Webhook插件参数,获取本次提交的分支信息
1.gitlab创建新应用 2.jenkins安装gitlab插件 3.插件安装完成后全局安全配置中使用并配置gitlab认证 4.注销重新登录后自动使用gitlab当前登录
一、部署jenkins master 1.创建Deployment YAML文件 apiVersion: apps/v1 kind: Deployment metadata: name: je
一、docker安装nexus wget https://mirrors.aliyun.com/docker-ce/linux/centos/docker-ce.repo yum clean all
一、新建library文件 build.groovy package org.devops // 构建类型 def Build(buildType,buildShell){
一、制品获取 1.安装及配置插件 配置插件(jenkins项目中) 2.选择对应的制品 3.修改jenkins file // 新增以下代码 String artifactU
1.github创建OAuth 2.jenkins安装并配置github认证插件 jenkins配置使用github认证 3.注销重新登录
一、添加测试Maven项目 1.新建一个gitlab项目 2.导入simple-java-maven-app仓库代码(可以去github或者Gittree上都有) 3.配置mvn 国内源
一、添加AnsiColor插件 二、查看插件语法 1.打开任意pipline项目配置,找到流水线语法,并点击 跳转连接,选择插件,查看帮助 三、修改sharelibrary脚本,优
一、Pipeline概念 1 node/agent(节点) 节点是一个机器,可以是Jenkins的master节点也可以是slave节点。通过node指定当前job运行的机器(这个是脚本式语法)。
一、插件备份和恢复 1.安装备份插件 重启系统后查看 2.配置周期备份 点击进入,点击Settings Backup only builds marked to keep
一、.部署LDAP 这里使用容器部署,手动部署参考:https://www.cnblogs.com/panwenbin-logs/p/16101045.html 1.安装docker wget -
由于sonarqube开源版本不支持多分支管理,在扫描所有分支的时候都会指定同一个sonar项目,不便于我们查看 一、下载开源插件 项目地址:https://github.com/mc1arke/
一、手动测试 注意此版本已经内置包含Java语言扫描插件,不再需要单独安装 1.clone代码 git clone git@192.168.1.128:root/demo-maven-serv
我有下一种情况。 从 PHP 表单中我只获得公司 ID 我需要使用该公司 ID 排列所有用户名 我需要数组并将具有该用户名的所有日志导出到表 我的问题是,当我尝试下一步时: $sql2 = "SELE
我是一名优秀的程序员,十分优秀!