秃头小白

并查集

01背包(1) bfs(4) dfs(6) dfs序讲解(1) Dijkstra算法优先队列优化(2) dp(7) KMP(1) LCA(4) STL(1) 二分(5) 二分图(3) 二进制(1) 二进制枚举(3) 优先队列(1) 倍增(2) 分治(2) 前缀和与差分(3) 区间dp(11) 博弈论(1) 图(1) 快速幂(1) 思维题(55) 数学题(7) 数论(2) 整除分块（数论）(1) 最小生成树(2) 有关约数（质因数等）的基础数论(2) 栈(1) 树吧(5) 树状dp(1) 树状数组(2) 树状数组+dfs序(2) 模拟(4) 滑动窗口(4) 状压dp(1) 离散化+并查集(1) 离散化讲解及入门例题(2) 签到题(2) 素数筛(1) 线段树(10) 贪心(12) 逆元(1) 逆序对的三种求法(1) 题解(16) 高精度(8)

/ 注册

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

CodeForces - 445B DZY Loves Chemistry 来自专栏

题目链接 https://codeforces.com/problemset/problem/445/B 解题思路我直接想错了，我居然在找最大的连通区域，原来即使小的连通区域也会有贡献，我直接忽略了，不知道自己为何如此傻X。思路：n-连通分支数，是化学药品反应的次数，2^(n-连通分支数)为答案。...

2020-11-17

1 696

修改数组（蓝桥）

题目链接 https://www.dotcpp.com/oj/problem2301.html 解题思路确实有点难理解。从简单的讲起：有这么一个思路，把已经被出现过的数构成的不连续的几段区间记录下来，比如用过了1，2，5，6，7，9，那么我们就记录下来区间[1,2]，[5,7]，[9,9]。判断当...

2020-10-12

1 568

小y的旅行

题目链接 https://ac.nowcoder.com/acm/contest/7780/C 解题思路并查集。大致思路：先把连接着两个大于k的点的边加入，再判断连接着小于等于k的两个点的边，两点是否同根，若同根则答案++，并且不将边加入；若不同根，则答案不变，并且加入边。两个点，其中存在至少一个...

2020-10-08

1 611

Wireless Network

题目连接 https://vjudge.net/contest/397891#problem/B密码：20201002 解题思路并查集，半个板子题。并查集讲解区别在于，本题并非一条边一条边的join的，而是每次插入一个点，让插入的这个点和已经插入的所有距离满足条件的点join，不满足的只标记插入，...

2020-10-03

1 548

畅通工程（并查集的基础讲解）

题目连接 http://acm.hdu.edu.cn/showproblem.php?pid=1232 题目大意多组样例输入，n座城市，m条路，问最少需要修多少条路能使全部城市相互可达。本质：求图的连通分支数。解题思路思路很明确，就是划分块，相互连通的属于同一块，最后数数多少块输出。难点在于如...

2020-08-28

1 847