Fizzmy

并查集

--------DP--------(1) CDQ分治(1) DP(11) FFT(4) z-box(6) 主席树(1) 二分(2) 分数规划(1) 分治(1) 区间DP(3) 博弈论(2) 后缀数组(2) 哈希(1) 学习笔记(2) 容斥(1) 强连通分量(1) 扫描线(1) 数位DP(3) 数论(12) 斯特林数(1) 暴力(2) 最小生成树(1) 最短路(1) 期望DP(4) 未归档(5) 树形dp(4) 模拟(1) 模板(3) 游记(1) 状态压缩(8) 线段树(12) 组合数学(1) 网络流(4) 脑洞(8) 莫比乌斯反演(2) 贡献法(3) 题解(2)

/ 注册

全部文章 / 并查集（共4篇）

Codechef MARCH14 GERALD07-莫队+并查集

传送门这道题也是bzoj3514离线版题意：给你n个点，m条边，询问k个区间[L,R]，求只保留[L,R]间的边，有多少个联通块。n,m,k<=200000 Solution：既然是离线那么显然可以搞事[滑稽]，询问区间有什么暴力方法呢？莫队！因为在图上所以每次操作不是 O（...

2021-08-18

0 384

HDU6074 Phone Call-并查集

题意：给你一棵树，m个条件，每个条件给出a,b,c,d,w，表示a到b和c到d路径上的点互相到达需要w的代价，现求从1号点出发能到达哪些点以及最小代价。 Solution：不难发现这是要构造一颗最小生成树，把w按照从小到大排一遍序，对于每个条件，求出a,b的LCA和c,d的LCA，把经过他...

2021-08-18

0 294

AtCoder AGC14E-Blue and Red Tree 并查集+启发式合并+STL

传送门题意：给出一颗树，初始每条边是蓝色，可以选择一条全是蓝色的路径，删去其中一条边，在这条路径的两个端点连上一条红色边，现给你两棵树，判断第一棵树能不能变成第二棵树（n<=1e5） Solution：我们只考虑蓝色边，注意到这是一棵树，所以每次删除一条边后会把图分成两部分，...

2021-08-18

0 442

HDU6109 数据分割-并查集+启发式合并

传送门题意：给出一些限制形如 xi≠xj x i ≠ x j 或 xi=xj x i = x j 判断最早出现矛盾的位置（n<=1e5） Solution：等于关系满足传递性，可以用并查集来维护而不等关系呢？可以这样做：把相等元素放在一个集合里，每个集合看做一个...

2021-08-18

0 414