种类并查集

P2024 [NOI2001] 食物链

类似于超级源点，把\(x+n\)丢进集合里，相当于\(x\)对这个集合作了标记，方便维护

细节

注意\(x\to y\)，对于\(y\to z\)，会有\(z\to x\)

这里会出现自己和自己连边的情况，用\(fa[rt]=0\)的写法需要特判

P6008 [USACO20JAN] Cave Paintings P

主要考察思维，毕竟实现超简单

一开始想根据合并的位置高度划分出一棵树，发现做不了

其实只需要从下往上维护连通块，遇到连通块间的合并，将方案数相乘，最后每个连通块方案数加\(1\)即可

带权并查集

维护连续编号

P1196 [NOI2002] 银河英雄传说

对于询问，我们要在并查集操作的基础上维护该点到根的距离

考虑合并\(x,y\)时，若将\(y\)并到\(x\)末尾，则\(y\)所在链头到\(x\)的链头的距离为\(siz[x]+1\)，用并查集的根维护链头，连一条权值为\(siz[x]+1\)的边即可

路径压缩和按秩合并都可实现

P3273 [SCOI2011]棘手的操作

所有操作都可以在线段树上实现，唯一的问题是编号不一定连续

由于每次操作的连通块都是一棵树，考虑变成编号连续的DFS序数组，问题变成合并两个编号连续的序列使新序列编号连续，直接将一个接到另一个末尾，重编号即可，用上面的做法就行了（其实直接启发式合并也能做）

可持久化并查集

标签：连通,合并,查集,链头,编号,维护
From： https://www.cnblogs.com/zhone-lb/p/18522223

并查集---Linux发行版的数量
题目描述Linux操作系统有多个发行版，distrowatch.com提供了各个发行版的资料。这些发行版互相存在关联，例如Ubuntu基于Debian开发，而Mint又基于Ubuntu开发，那么我们认为Mint同Debian也存在关联。发行版集是一个或多个相关存在关联的操作系统发行版，集合内不包含没有关联的发行......
计蒜客：修建大桥(并查集/DFS/BFS）
找到有几张连通图即可解决问题。DFS：1#include<bits/stdc++.h>2usingnamespacestd;3intn,m;4intgraph[1005][1005]={0};5boolvisited[1005]={false};6voiddfs(intp){7if(visited[p]){8return;9}10visited[p]......
算法-并查集
1.寻找图中是否存在路径(LeetCode1971)有一个具有n个顶点的双向图，其中每个顶点标记从0到n-1（包含0和n-1）。图中的边用一个二维整数数组edges表示，其中edges[i]=[ui,vi]表示顶点ui和顶点vi之间的双向边。每个顶点对由最多一条边连接，并且没有顶点存在与......
【并查集】【中间值范围】NOIP2017]奶酪
https://ac.nowcoder.com/acm/contest/22904/1027开了ll还见祖宗注意x^2+y2算完之后先判断有没有超4r2的范围，没有的话再计算z^2，算是对longlong溢出的特判#include<bits/stdc++.h>typedeflonglongll;usingnamespacestd;classUnionFind{public:UnionFind(ll......
【寻迹#4】并查集
并查集一、并查集并查集是一种用于管理元素所属集合的数据结构，实现为一个森林，其中每棵树表示一个集合，树中的节点表示对应集合中的元素。顾名思义，并查集支持两种操作：合并（Union）：合并两个元素所属集合（合并对应的树）查询（Find）：查询某个元素所属集合（查询对应的树的根节点），这可以用于判......
并查集
并查集并查集是一种数据结构，它主要处理一些不相交集合的合并问题。一些常见的用途有求连通子图、最小生成树Kruskal算法和求公共祖先等。并查集的主要操作有：初始化Init查询Find合并Union初始化Init()voidInit(intn){vector<int>father(n+1);//创......
经典算法思想--并查集
前言（最近在学习Java，所有函数都是用Java语言来书写的）前言部分是一些前提储备知识在并查集（Union-Find）数据结构中，rank（中文称为“秩”）是用来表示树的高度或深度的一种辅助信息。它的主要作用是优化合并操作，以保持并查集的结构尽可能扁平，从而提高查询效率。秩的具体定义......
CF771A. Bear and Friendship Condition 题解并查集
题目链接：https://codeforces.com/problemset/problem/771/A视频讲解：https://www.bilibili.com/video/BV1tZ1FYPELp/?p=6题目大意：判断一个无向图中的每个连通块是否都是一个完全图。首先我们可以用并查集维护每个连通块的大小。其次，我们可以开一个\(cnt_i\)表示以节点\(i\)......
CF1139C. Edgy Trees 题解并查集
题目链接：https://codeforces.com/problemset/problem/1139/C视频讲解：https://www.bilibili.com/video/BV1tZ1FYPELp?p=3我们可以求总方案数-不满足条件的方案数。设一个不包含黑色边的极大连通块的大小为\(sz_i\)。则答案为\[n^k-\sum\{sz_i^k\}\]示例程序：#include......
CF1800E2. Unforgivable Curse (hard version) 题解并查集
题目链接：https://codeforces.com/contest/1800/problem/E2视频讲解：https://www.bilibili.com/video/BV1tZ1FYPELp?p=2把下标\(i\)对应到图中编号为\(i\)的节点。节点\(i\)和\(i+k\)之间连一条边，节点\(i\)和\(i+k+1\)之间也连一条边。同一个连通块里的节点对应的字......

并查集