青烟绕指柔

并查集

2-SAT(1) bfs(6) Codeforces(3) dfs(4) Hash(1) HDU(2) KM(1) LCA(2) Link_Cut_Tree(1) LIS(1) Splay(1) STL(7) WQS二分(1) 中等难度(6) 主席树(4) 二分(1) 分块(1) 前缀和(1) 动态规划(15) 博弈论(1) 双连通分量(1) 图论(158) 堆(3) 字符串(5) 差分(1) 拓扑排序(4) 数位dp(3) 数学(1) 数论(12) 无旋treap(2) 最小环(2) 最小生成树(11) 最短路(18) 树形dp(1) 树状数组(16) 树结构(4) 树链剖分(1) 概率dp(2) 相对大小问题(1) 矩阵乘法(3) 离线算法(12) 线性基(2) 线段树(28) 背包问题(2) 莫队(1) 计算几何(8) 贪心(2) 距离表示(1) 题解(4)

/ 注册

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

[HNOI2012]永无乡

题目描述永无乡包含 nn 座岛，编号从 11 到 nn ，每座岛都有自己的独一无二的重要度，按照重要度可以将这 nn 座岛排名，名次用 11 到 nn 来表示。某些岛之间由巨大的桥连接，通过桥可以从一个岛到达另一个岛。如果从岛 aa 出发经过若干座（含 00 座）桥可以到达岛 bb ，则称岛 a...

2019-12-27

0 427

可持久化并查集

昨日做题时，见久不作过可持久化并查集矣，将忘光矣，乃有此博客。可持久化并查集和普通并查集差不多，只是多了一个回退的操作。一般支持的操作为： a b 合并a,b所在集合 k 回到第k次操作之后的状态(查询算作操作) a b 询问a,b是否属于同一集合，是则输出1否...

2019-12-27

0 420

抓捕盗窃犯

题目链接：抓捕盗窃犯仔细想一下图的构成就可以看出，一个点一个出度，所以对于每一个联通块比构成环，在环上随便一个点设置哨卡就能抓到联通块所有人。所以我们找到m个最大的联通块即可。更复杂的图可以用Tarjan，但是我们这道题直接并查集即可。 AC代码： #include<bit...

2019-12-27

0 378