参考内容：
图论——并查集(详细版)
并查集（Disjoint-set）是一种精巧的树形数据结构，它主要用于处理一些不相交集合的合并及查询问题。一些常见用途，比如求联通子图、求最小生成树的 Kruskal 算法和求最近公共祖先（LCA）等。
并查集的理念是只关注个体属于哪个阵营，并不关心这个阵营中个体内部的关系，比如我们常说的张三是李家沟的，王二是王家坝的。同时并查集借助个体代表集体的思想，用一个元素代表整个群体，就像我们开学都会有学生代表、教师代表讲话一样，在台上讲话的那一个学生就代表了学校所有的学生。
并查集基本操作
并查集的基本操作主要有初始化 init、查询 find和合并 union操作。
初始化
在使用并查集的时候，常常使用一个数组fa来存储每个元素的父节点，在一开始的时候所有元素与其它元素都没有任何关系，即大家相互之间还不认识，所以我们把每个元素的父节点设为自己。
#define ARR_LEN 6000
int fa[ARR_LEN];
void init(int n)
{
for(int i = 1; i <= n; i++)
fa[i] = i;
}
查询
查询即找到指定元素的祖先。需要注意的是，这里我们需要找到指定元素的根祖先，不能找到爸爸或者爷爷就停止了，而是要找到查找不下去了为止，所以要不断的去递归下去，直到找到父亲为自己的结点才结束。
int find(int i)
{
if(i == fa[i]) // 递归出口
return i;
else
return find(fa[i]); // 不断向上查找祖先
}
考虑下面的场景，假如第一次我们需要查询元素5的祖先，第二次需要查询元素4的祖先，会发现第一次查询包含了第二次查询的计算过程，但我们的程序却傻傻的计算了两次，有没有办法去来优化查询过程，让每一次查询都能利用到此前查询计算的便利？
考虑到并查集并不关心某个元素的爸爸、爷爷是谁，只关心最终的祖先是谁，所以我们可以在查询的过程中顺便做一些修改，比如在查询5的过程中，顺便就把4和2的父亲给修改为1，即我们在查找过程中进行路经压缩
int find(int i)
{
if(i == fa[i]){
return i;
} else {
fa[i] = find(fa[i]); // 进行路径压缩
return fa[i];
}
}
合并
合并操作即介绍两个人相互认识，将他们纳入同一个帮派，只需要将俩元素的父亲修改为同一个即可。
void union(int i, int j)
{
int fa_i = find(i);
int fa_j = find(j);
fa[fa_i] = fa_j;
}
相关练习题目
洛谷 P1551 亲戚
题目连接：https://www.luogu.com.cn/problem/P1551
题目描述
若某个家族人员过于庞大，要判断两个是否是亲戚，确实还很不容易，现在给出某个亲戚关系图，求任意给出的两个人是否具有亲戚关系。
规定：xxx 和 yyy 是亲戚，yyy 和 zzz 是亲戚，那么 xxx 和 zzz 也是亲戚。如果 x，yx，yx，y 是亲戚，那么 xxx 的亲戚都是 yyy 的亲戚，yyy 的亲戚也都是 xxx 的亲戚。
输入格式
第一行：三个整数 n,m,p，(n,m,p≤5000)n,m,p，(n,m,p≤5000)n,m,p，(n,m,p≤5000) 分别表示有 nnn 个人，mmm 个亲戚关系，询问 ppp 对亲戚关系。
以下 mmm 行：每行两个数 Mi，Mj，1≤Mi，Mj≤nM_i，M_j，1≤M_i，M_j≤nMi，Mj，1≤Mi，Mj≤n，表示 MiM_iMi 和 MjM_jMj 具有亲戚关系。
接下来 ppp 行：每行两个数 Pi，PjP_i，P_jPi，Pj，询问 PiP_iPi 和 PjP_jPj 是否具有亲戚关系。
输出格式
ppp 行，每行一个Yes或No。表示第 iii 个询问的答案为“具有”或“不具有”亲戚关系。
输入输出样例
# 输入
6 5 3
1 2
1 5
3 4
5 2
1 3
1 4
2 3
5 6
# 输出
Yes
Yes
No
题目解析
可以发现这是一个非常标准的并查集问题，简直和并查集模版如出一辙，因此直接将所有关系读取后进行合并，然后直接查询父亲是否为同一个即可。
#include<bits/stdc++.h>
using namespace std;
#define ARR_LEN 6000
int fa[ARR_LEN];
void init(int n)
{
for(int i = 1; i <= n; i++)
fa[i] = i;
}
int find(int i)
{
if(i == fa[i]){
return i;
} else {
fa[i] = find(fa[i]);
return fa[i];
}
}
void union(int i, int j)
{
int fa_i = find(i);
int fa_j = find(j);
fa[fa_i] = fa_j;
}
int main()
{
int n, m, p;
int a, b;
cin>> n >> m >> p;
init(n);
for(int i = 0; i < m; i++){
cin >> a >> b;
union(a, b);
}
for(int i = 0; i < p; i++){
cin >> a >> b;
int fa_a = find(a);
int fa_b = find(b);
if(fa_a == fa_b)
cout<<"Yes"<<endl;
else
cout<<"No"<<endl;
}
}
杭电 OJ1213 How Many Tables
题目连接：https://acm.hdu.edu.cn/showproblem.php?pid=1213
题目描述
Today is Ignatius' birthday. He invites a lot of friends. Now it's dinner time. Ignatius wants to know how many tables he needs at least. You have to notice that not all the friends know each other, and all the friends do not want to stay with strangers.
One important rule for this problem is that if I tell you A knows B, and B knows C, that means A, B, C know each other, so they can stay in one table.
For example: If I tell you A knows B, B knows C, and D knows E, so A, B, C can stay in one table, and D, E have to stay in the other one. So Ignatius needs 2 tables at least.
输入格式
The input starts with an integer T(1<=T<=25)T(1<=T<=25)T(1<=T<=25) which indicate the number of test cases. Then TTT test cases follow. Each test case starts with two integers NNN and M(1<=N,M<=1000)M(1<=N,M<=1000)M(1<=N,M<=1000). NNN indicates the number of friends, the friends are marked from 111 to NNN. Then MMM lines follow. Each line consists of two integers AAA and B(A!=B)B(A!=B)B(A!=B), that means friend AAA and friend BBB know each other. There will be a blank line between two cases.
输出格式
For each test case, just output how many tables Ignatius needs at least. Do NOT print any blanks.
输入输出样例
# 输入
2
5 3
1 2
2 3
4 5
5 1
2 5
# 输出
2
4
题目解析
分析可以发现，这个问题要我们做的是统计在所有元素合并之后，统计总共有多个和集合。很轻松就能写出下面的 AC 代码。类似的问题还有杭电 OJ1232 畅通工程。
读者大人可以在此基础上继续进行延伸，我们实际生活中每个桌子只能坐 8 个人，假设还需要考虑每桌人数的容量，又如何进行改进呢？
#include<bits/stdc++.h>
using namespace std;
#define ARR_LEN 6000
int fa[ARR_LEN];
void init(int n)
{
for(int i = 1; i <= n; i++)
fa[i] = i;
}
int find(int i)
{
if(i == fa[i]){
return i;
} else {
fa[i] = find(fa[i]);
return fa[i];
}
}
void union(int i, int j)
{
int fa_i = find(i);
int fa_j = find(j);
fa[fa_i] = fa_j;
}
int main()
{
int n, m, a, b, t;
cin>>t;
for(int i = 0; i < t; i++){
cin>>n>>m;
int ans = 0;
init(n);
for(int i = 0; i < m; i++) {
cin>>a>>b;
union(a, b);
}
for(int i = 1; i <= n; i++) {
// 如果父亲是自己，那么就表示一个独立的集合
if(find(i) == i)
ans++;
}
cout<<ans<<endl;
}
}
杭电 OJ1272 小希的迷宫
题目连接：https://acm.hdu.edu.cn/showproblem.php?pid=1272
题目描述
小希设计了一个迷宫让 Gardon 玩，首先她认为所有的通道都应该是双向连通的，就是说如果有一个通道连通了房间 A 和 B，那么既可以通过它从房间 A 走到房间 B，也可以通过它从房间 B 走到房间 A，为了提高难度，小希希望任意两个房间有且仅有一条路径可以相通（除非走了回头路）。小希现在把她的设计图给你，让你帮忙判断她的设计图是否符合她的设计思路。比如下面的例子，前两个是符合条件的，但是最后一个却有两种方法从 5 到达 8。
输入格式
输入包含多组数据，每组数据是一个以 0 0 结尾的整数对列表，表示了一条通道连接的两个房间的编号。房间的编号至少为 1，且不超过 100000。每两组数据之间有一个空行。整个文件以两个 -1 结尾。
输出格式
对于输入的每一组数据，输出仅包括一行。如果该迷宫符合小希的思路，那么输出Yes，否则输出No。
输入输出样例
# 输入
6 8 5 3 5 2 6 4
5 6 0 0
8 1 7 3 6 2 8 9 7 5
7 4 7 8 7 6 0 0
3 8 6 8 6 4
5 3 5 6 5 2 0 0
-1 -1
# 输出
Yes
Yes
No
题目解析
其实这个问题就是让我们判断一个连通图中是否存在环，那么问题就转换为寻找出现环的条件。其实不难发现出现下面两种情况时，连通图即存在环。
在查找过程中，发现两个不同元素的父亲是相同的；
若不存在环，则边的数量一定比顶点数量少 1。
#include<bits/stdc++.h>
using namespace std;
#define ARR_LEN 100010
int fa[ARR_LEN];
bool visited[ARR_LEN]; // 用于辅助记录顶点的数量
int edges, points; // 记录顶点和边的数量
bool hascycle; // 是否存在环
void init()
{
hascycle = false;
edges = 0;
points = 0;
for(int i = 1; i < ARR_LEN; i++)
fa[i] = i, visited[i] = false;
}
int find(int i)
{
if(i == fa[i]){
return i;
} else {
fa[i] = find(fa[i]);
return fa[i];
}
}
void union(int i, int j)
{
int fa_i = find(i);
int fa_j = find(j);
// 两个元素祖先相同，存在环
if(fa_i == fa_j) {
hascycle = true;
} else {
visited[i] = true;
visited[j] = true;
edges++;
fa[fa_i] = fa_j;
}
}
int main()
{
int a, b;
init();
while(cin>>a>>b) {
if(a == 0 && b == 0) {
cout<<"Yes"<<endl;
continue;
}
if(a == -1 && b == -1) {
return 0;
}
union(a, b);
while(cin>>a>>b){
if(a == 0 && b == 0) {
break;
}
union(a, b);
}
if(hascycle) {
cout<<"No"<<endl;
continue;
}
for(int i = 1; i < ARR_LEN; i++){
if(visited[i]) {
points++;
}
}
if(points == edges + 1) {
cout<<"Yes"<<endl;
} else {
cout<<"No"<<endl;
}
init();
}
}
Read More ~
《算法竞赛进阶指南》165 小猫爬山题解
参考内容：
[洛谷][noip][算法竞赛进阶指南]小猫爬山
《算法竞赛进阶指南》小猫爬山
小猫爬山
题目描述
题目链接：https://www.acwing.com/problem/content/167/
Freda 和 Rainbow 饲养了 N 只小猫。这天，小猫们要去爬山。经历了千辛万苦，小猫们终于爬上了山顶，但是疲倦的它们再也不想徒步走下山了（呜咕>_<）。
Freda 和 Rainbow 只好花钱让它们坐索道下山。索道上的缆车最大承重量为 W，而 N 只小猫的重量分别是C1、C2……Cn。当然，每辆缆车上的小猫的重量之和不能超过 W。每租用一辆缆车，Freda 和 Rainbow 就要付 1 美元，所以他们想知道，最少需要付多少美元才能把这 N 只小猫都运送下山？
输入格式
第一行包含两个用空格隔开的整数，N 和 W。接下来 N 行每行一个整数，其中第 i+1 行的整数表示第 i 只小猫的重量 Ci。
输出格式
输出一个整数，最少需要多少美元，也就是最少需要多少辆缆车。
分析解答
贪心
经过思考发现，我们只需要尽可能的在每辆车上都放更多的小猫，就能以最经济的方式把所有小猫都送下山。所以是一个非常明显的贪心题目，我们将所有小猫按重量排序，尽可能把肥猫先送下山即可。具体实现代码如下：
#include<bits/stdc++.h>
using namespace std;
void cin_arr(int *num, int len)
{
for(int i = 0; i < len; i++){
cin>>num[i];
}
}
int slove(int *num, int n, int w)
{
int ans = 0;
int remain = 0;
int load = 0;
sort(num, num+n);
while(true){
for(int i = 0; i < n; i++){
// 连当前最小的猫都装不下，那么就新开一辆车
if(num[i] != -1 && remain < num[i]){
ans++;
remain = w;
break;
}
}
for(int i = n-1; i >= 0; i--){
// 从大到小查找，尽可能装肥猫
if(num[i] != -1 && remain >= num[i]){
remain -= num[i];
// 运送走的小猫重量以 -1 表示
num[i] = -1;
load++;
break;
}
}
// 如果所有小猫都运走了，那么当前 ans 就是答案
if(load >= n)
return ans;
}
}
int main()
{
int n, w;
int cat[1000000];
cin>>n>>w;
cin_arr(cat, n);
cout<<slove(cat, n, w)<<endl;
}
经过实际测试发现，盲目使用贪心思想的算法并不正确，例如如下测试用例。
6 16
9 5 5 5 4 3
贪心的结果是使用 3 辆车，分别为9+5、5+5+4、3；而正确的结果却是使用 2 辆车，分别为9+4+3和5+5+5。
深度优先搜索
既然贪心思想在这里行不通，那么我们就采用暴力搜索，即小猫可以放在现有任意一辆车上。具体实现代码如下：
#include<bits/stdc++.h>
using namespace std;
#define N 2000
int n, w;
int cat[N];
int sum[N] = {0}; // 第 i 辆车当前重量
int ans = N;
void cin_arr(int *num, int len)
{
for(int i = 0; i < len; i++){
cin>>num[i];
}
}
void dfs(int cur_cat, int cur_car)
{
if(cur_car > ans) // 求最小值，不符合直接返回
return ;
if(cur_cat == n) { // 所有小猫都上车了
ans = cur_car;
return ;
}
for(int i = 0; i < cur_car; i++) {
if(sum[i] + cat[cur_cat] <= w) { // 当前猫能放进去
sum[i] += cat[cur_cat]; // 当前猫占用重量
dfs(cur_cat+1, cur_car); // 继续放下一只猫
sum[i] -= cat[cur_cat]; // 把已经放进去的猫拿出来，因为是循环，所以放入下一辆车里面
}
}
// 新开一辆车，把当前这只猫放到新的车里面
sum[cur_car] = cat[cur_cat];
dfs(cur_cat+1, cur_car+1);
sum[cur_car] = 0; // 把猫拿出来
}
int main()
{
cin>>n>>w;
cin_arr(cat, n);
dfs(0, 0);
cout<<ans<<endl;
}
搜索优化
考虑到每次都是在车数量固定的情况下进行搜索的，那么少满足一次(sum[i] + cat[cur_cat] <= w)条件，就会少一次递归的调用，也即少一次搜索。那么如何能尽快使得程序尽快不满足该条件呢？
让sum[i]减小的速度加快就会减少搜索分支，即每次放更重一点的猫进去，就能达到效果。所以我们可以在进行搜索前将小猫的重量进行降序排序，这样从肥猫开始搜索就会减少分支。
#include<bits/stdc++.h>
using namespace std;
#define N 2000
int n, w;
int cat[N];
int sum[N] = {0}; // 第 i 辆车当前重量
int ans = N;
void cin_arr(int *num, int len)
{
for(int i = 0; i < len; i++){
cin>>num[i];
}
}
bool cmp(int a, int b)
{
return a > b;
}
void dfs(int cur_cat, int cur_car)
{
if(cur_car > ans) // 求最小值，不符合直接返回
return ;
if(cur_cat == n) { // 所有小猫都上车了
ans = cur_car;
return ;
}
for(int i = 0; i < cur_car; i++) {
if(sum[i] + cat[cur_cat] <= w) { // 当前猫能放进去
sum[i] += cat[cur_cat]; // 当前猫占用重量
dfs(cur_cat+1, cur_car); // 继续放下一只猫
sum[i] -= cat[cur_cat]; // 把已经放进去的猫拿出来，因为是循环，所以放入下一辆车里面
}
}
// 新开一辆车，把当前这只猫放到新的车里面
sum[cur_car] = cat[cur_cat];
dfs(cur_cat+1, cur_car+1);
sum[cur_car] = 0; // 把猫拿出来
}
int main()
{
cin>>n>>w;
cin_arr(cat, n);
sort(cat, cat+n, cmp); // 反排序优化搜索
dfs(0, 0);
cout<<ans<<endl;
}
Read More ~
二叉树的前序、中序、后序、层序遍历
参考内容：
五分钟让你彻底理解二叉树的非递归遍历
Python实现二叉树的非递归遍历
二叉树遍历——深度优先（前中后序）+广度优先（层序遍历）
构造二叉树
定义二叉树结构如下
struct node
{
int data;
node *left;
node *right;
};
构造如下形态二叉树
node *init_tree()
{
node *node1 = (node *)malloc(sizeof(node));
node *node2 = (node *)malloc(sizeof(node));
node *node3 = (node *)malloc(sizeof(node));
node *node4 = (node *)malloc(sizeof(node));
node *node5 = (node *)malloc(sizeof(node));
node *node6 = (node *)malloc(sizeof(node));
node *node7 = (node *)malloc(sizeof(node));
node *node8 = (node *)malloc(sizeof(node));
node1->data = 1;
node2->data = 2;
node3->data = 3;
node4->data = 4;
node5->data = 5;
node6->data = 6;
node7->data = 7;
node8->data = 8;
node1->left = node2;
node1->right = node3;
node2->left = node4;
node2->right = node5;
node3->right = node6;
node5->left = node7;
node5->right= node8;
return node1;
}
前序遍历（递归）
前序遍历顺序为根左右。要遍历整个二叉树我们就需要遍历二叉树的每一个子树，对于任何一个子树它的遍历方式均为根左右顺序遍历。即所有子问题均与父问题除规模大小不同外，其余均相同。所以可以采用递归方式实现前序遍历。
// 前序遍历 根左右
void pre_order_traversal(node *root)
{
if(root) {
cout<<root->data<<" ";
pre_order_traversal(root->left);
pre_order_traversal(root->right);
}
}
遍历结果为：1 2 4 5 7 8 3 6
中序遍历（递归）
中序遍历顺序为左根右。其与前序遍历仅顺序不同，其余均相同。
// 中序遍历 左根右
void in_order_traversal(node *root)
{
if(root) {
in_order_traversal(root->left);
cout<<root->data<<" ";
in_order_traversal(root->right);
}
}
遍历结果为：4 2 7 5 8 1 3 6
后序遍历（递归）
后序遍历顺序为左右根。其与前序、中序遍历仅顺序不同，其余均相同。
// 后序遍历 左右根
void post_order_traversal(node *root)
{
if(root) {
post_order_traversal(root->left);
post_order_traversal(root->right);
cout<<root->data<<" ";
}
}
遍历结果为：4 7 8 5 2 6 3 1
前序遍历方法一（非递归）
因为递归实际上是由系统帮我们进行压栈，所以理论上所有递归算法都可以改为循环+栈实现，那么我们先照着上述前序遍历的样子修改为循环+栈的形态。需要注意的是由于栈先进后出的特性，为了保证左孩子在右孩子前被访问，所以应该先右孩子入栈，再左孩子入栈。
// 前序遍历 根左右
void pre_order_traversal(node *root)
{
stack<node *> s;
s.push(root);
while(!s.empty()) {
node *cur = s.top();
s.pop();
if(cur) {
cout<<cur->data<<" ";
s.push(cur->right);
s.push(cur->left);
}
}
}
遍历结果为：1 2 4 5 7 8 3 6
前序遍历方法二（非递归）
现在我们换一种思路来实现前序非递归遍历，仔细观察前序遍历的递归调用过程。
先把从根结点开始的所有左子树放入栈中；
弹出栈顶元素
如果栈顶元素有右子树，那么右子树入栈
重复上述过程直到栈为空
因此我们可以写出遍历代码
// 前序遍历 根左右
void pre_order_traversal(node *root)
{
stack<node *> s;
node *cur = root;
while(cur || !s.empty()) {
// 将左子树全部入栈
while(cur) {
cout<<cur->data<<" ";
s.push(cur);
cur = cur->left;
}
if(!s.empty()) {
cur = s.top();
s.pop();
cur = cur->right;
}
}
}
遍历结果为：1 2 4 5 7 8 3 6
中序遍历（非递归）
有了前面的基础，我们再来考虑中序遍历，会发现中序遍历与前序遍历只是打印结点的位置不一样。前序遍历是在结点入栈时打印，中序遍历只需要替换为在结点出栈时打印即可。
// 中序遍历 左根右
void in_order_traversal(node *root)
{
stack<node *> s;
node *cur = root;
while(cur || !s.empty()) {
// 将左子树全部入栈
while(cur) {
s.push(cur);
cur = cur->left;
}
if(!s.empty()) {
cur = s.top();
cout<<cur->data<<" ";
s.pop();
cur = cur->right;
}
}
}
遍历结果为：4 2 7 5 8 1 3 6
后序遍历方法一（非递归）
后序遍历相对来说显得更加复杂了。在前序和中序遍历中，只要左子树处理完毕实际上栈顶元素就可以出栈了，但后序遍历需要把左子树和右子树都处理完毕才能出栈，显然我们需要某种方法记录遍历的过程。
实际上我们只需要记录下遍历的前一个结点就能解决问题，因为通过前一个结点我们可以做如下判断：
如果前一个结点是当前结点的右子树，那么说明右子树已经遍历完毕可以出栈了
如果前一个结点是当前结点的左子树而且当前结点没有右子树，那么说明可以出栈了
如果当前结点即没有左子树也没有右子树，即为叶子结点，那么说明可以出栈了
若不属于上述情况，则依次将当前结点的右孩子和做孩子入栈，这样就能保证每次取栈顶元素时，左孩子都在右孩子前面被访问，左孩子和右孩子都在父结点前面被访问。
// 后序遍历 左右根
void post_order_traversal(node *root)
{
stack<node *> s;
node *pre = NULL;
node *cur = root;
s.push(cur);
while(!s.empty()) {
cur = s.top();
// 叶子结点
if((!cur->left && !cur->right) // 叶子结点
|| pre == cur->right // 前一个结点为当前结点右子树
|| (pre == cur->left && !cur->right)) { // 前一个结点为当前结点左子树，且没有右子树
cout<<cur->data<<" ";
pre = cur;
s.pop();
} else {
if(cur->right)
s.push(cur->right);
if(cur->left)
s.push(cur->left);
}
}
}
遍历结果为：4 7 8 5 2 6 3 1
后序遍历方法二（非递归）
后序遍历的顺序是左右根，如