开拓计划4 - 二叉树与并查集
二叉树
二叉树的概念
- Q：什么是树？
- A：一种有 \(n\) 个节点最多有 \(n-1\) 条边的图。
- Q：什么是二叉树？
- A：每个节点都最多只有两个子节点的树。
二叉树和递归
-
Q：二叉树和递归有什么关系？
-
A：在执行递归的时候总是会自己调用自己，每一次调用都会产生新的一层，新的这几个需要执行的函数就成为了当前节点的子节点，一颗递归树就能画出来。
NKOJ 4376 遍历二叉树1
思路：二叉树的入门应用。
实现方法
- 先序遍历是根左右，中序遍历是左根右，后序遍历是左右根。
- 按照顺序，执行输出，向左递归，向右递归。
注意事项
- 在遍历二叉树时，注意是从根节点开始，不是从 \(1\) 号结点开始。
NKOJ 3909 遍历二叉树2
思路：二叉树的简单应用。
实现方法
- 用先序确定根节点，再通过中序，确定哪些是左子树，那些是右子树。
- 左右分别递归下去，要求后续，递归写完再输出。
注意事项
- 注意递归时不要把自己也递归了。
NKOJ 8599 无根树
思路：二叉树的简单应用。
实现方法
- 简单地从根节点开始递归遍历二叉树，每深入一层记录层数的
k就 \(+1\) 每次取k的最大值。
注意事项
- 一定不要用邻接矩阵存储二叉树，会
TLE。
并查集
对并查集的一些看法
- 并查集虽然是和集合有关，但是并没有遵循数学中对集合的严格规定，表达的更多是一种节点与节点之间的关系。
并查集的原理
-
Q：并查集的使用场景和理论基础是什么？
-
A：在二叉树中，每个节点都有自己的父节点(可以认为根节点的父节点是它自己)，如果题目给了节点之间的关系(不一定是从属关系)，就可以把两个节点放在同一棵二叉树里，如果要找两个节点在不在同一个集合，只需要找它们的父亲节点是否相同。
-
Q：并查集如何存储？
-
A：由于并查集需要经常找父亲，所以我们在数组中存储每个节点的父节点编号，初始时每个节点的父节点是它自己。
-
Q：并查集如何查找？
-
A：不断地向上递归，只要当前节点有父就继续想上找父节点，直到找到根节点就返回。
-
Q：并查集如何合并？
-
A：有两个节点要合并，就先判断是否在同一个集合中，如果不在就将一个的根节点变成另一个的根节点。
并查集的路径压缩
- Q：为什么要路径压缩？
- A：当并查集的所有节点成一条链状的时候，向上查找的时间复杂度会达到 \(O_n\) 我们无法接受，采用路径压缩优化。
- Q：路径压缩怎么写？
- A：当我要向上找一个节点的父节点只要找到祖宗，就将它的父节点直接设为祖宗节点(有点像一个城市要向中央汇报工作，要先向省级政府汇报，但如果是直辖市就可以直接跳过省级政府)。
并查集模板代码
int fa[20005];
int find(int x){
if(fa[x]==x) return x;
return fa[x]=find(fa[x]);//路径压缩
}
//核心找父节点
void merge(int x,int y){
int fx=find(x);
int fy=find(y);
if(fx!=fy) fa[fx]=fy;
}
bool same(int x,int y){
return find(x)==find(y);
}
void init(){
for(int i=1;i<=n;i++) fa[i]=i;
}
NKOJ 1205 亲戚
思路：并查集模板题
NKOJ 3197 岛屿
思路：并查集模板题
NKOJ 5614 加点
思路：可以直接到的加一个并查集，一共有几个并查集
NKOJ 2081 学外语
思路：会同一种语言的员工加一个并查集，一共有几个并查集
NKOJ 5681 交换排列
思路：一道看着像思维题的并查集
实现方法
- 能交换的两个点之间连一条边，计算有多少个点和它应该在的位置不在同一个集合中。
带权并查集
带权并查集的原理
- Q：带权并查集的原理是什么？
- A：带权并查集，是在常规的并查集的基础上给每一个点都加上了权值，并在路径压缩和合并的时候更新。给每一个点都带上权值，大大提升了并查集的作用范围。
- Q：权值可以带什么？
- A：一般可以带区间和、区间和的奇偶性、点与点之间的关系 etc.
带权并查集的模板代码
以求区间和为例
void getf(int x){
if(f[x]!=x){
int t=f[x];
f[x]=getf(f[x]);
val[x]+=val[t];//更新权值
}
return f[x];
}
void merge(int x,int y,int v){
int fx=getf(x),fy=getf(y);
if(fx==fy) return;
f[fx]=fy;
val[fx]=val[y]-val[x]+v;
}
时光倒流思想
- Q：什么是时光倒流思想？
- A：时光倒流思想，是将所有的输入数据输入进来，发现用题目告诉我们的方法直接用数据结构模拟难以实现(如并查集难以实现删边)，将数据倒序操作变成原来的相反操作(如并查集的删边变成加边)。
NKOJ 5682 果老师炸桥
题意
- 对于一个无向图，每次删一条边，求每次删完后有多少对点无法互相到达。
思路：带权并查集+时光倒流
实现方法
- 每次合并时将集合大小一同进行合并，每删一次边就会有那两个集合内的点两两不可达。
- 由于可撤销并查集，代码多时间高，于是采用时光倒流和简单带权并查集。
NKOJ 2281 方块游戏
思路：带权并查集
实现方法
- 用两个数组分别记录当前方块堆的高度，和距离根节点的距离，只有这样才能使用路径压缩。
- 每次在
getf函数中更新距离根节点的距离，在merge函数中更新dis和hgt。把距离根节点的距离加上堆在它顶上那一堆原来的高度，高度也加上那一堆的高度，把被移动后的高度归零。 - 每次查询的时候要先跑一遍
getf，类似于线段树的下放懒标记的操作。