当前位置: 首页 > news >正文

洛谷P1525 [NOIP 2010 提高组] 关押罪犯(恭喜解锁拆点并查集!!)

题目来源:https://www.luogu.com.cn/problem/P1525
答案导航:https://www.luogu.com.cn/record/230217157

没有学过拆点并查集,想了很久,用普通并查集+map(map用于维护互斥的点),但是有很多细节要抠,真的很复杂,A不出来啊!
呜呜呜无奈之下去找了ai老师解锁新区域了————拆点并查集(似乎也叫拓展域并查集?这个是二倍拓展,貌似可以几倍?
这道题是非常非常简单的一道几乎是拆点并查集的入门题,几乎一套就过没阻碍
那么就贴一下它和普通并查集比起来的核心增加处:
void uunion(int u, int v) { u = find(u); v = find(v); if (u == v) { return; } pp[u] = v; }以及在主函数里的:
uunion(p[i].a + N, p[i].b); uunion(p[i].a, p[i].b + N);

http://www.sczhlp.com/news/9678/

相关文章:

  • Score Matching
  • 对象转原始值
  • 通达信配色
  • I2C通信接口 VK2C22B 高抗干扰LED驱动段码液晶驱动芯片
  • 【自学嵌入式:stm32单片机】EXTI外部中断
  • Dify入门系列(1)| Dify 是什么?真能开启低代码 AI 应用开发?
  • 题解:P4368 [Code+#4] 喵呜
  • vue3 vue3-form-element表单生成工具
  • Codeforces 1042G Wafu! 题解 [ 绿 ] [ 数学 ] [ 线性 DP ] [ 前缀和 ] [ 暴力枚举 ]
  • 第二章:Linux基础命令
  • 题解:P4779 【模板】单源最短路径(标准版)
  • 事倍功半是蠢蛋39 cursor 报错user is unauthorized
  • 一个不错的AI写作工具
  • 2025CSP-S模拟赛33 比赛总结
  • 彩笔运维勇闯机器学习--一元线性回归
  • CAD_图纸文件拖动到CAD软件里面无法打开的解决办法
  • 使用spaCy和Thinc构建可训练关系抽取组件
  • xlsxio全平台(x86、arm32、arm64 )编译、测试,使用编译脚本10分钟快速编译!
  • vue3开发相关工具
  • Uncaught ReferenceError: Cannot access store before initializatio
  • echarts 流程图
  • 2025 暑假集训 Day6
  • rdi、rsi、rdx、rcx 是四个常用的64位通用寄存器
  • 浮点数的应用
  • Solidity-102摘要记录
  • DLM(Diffusion Language Model) vs AR(Autoregressive)
  • django之中间件 - 实践
  • 使用DOMPurify防止存储型XSS
  • 关于redis的原子性简要介绍
  • 剪映破解版 5.9.0版本(不可升级,可以登录账号)