本节概要：
课程链接：戳这 <—（您的支持是我最大的动力！）
一、dfs 搜树 + 剪枝
在搜树之前肯定是需要把树存起来的，在这里我们用
v
e
c
t
o
r
vector
vector 来存树，以无向边举例，下面介绍一个通用的搜树模板：
- 存树的代码：
vector<int> c[N];
cin>>n;
for(int i=1;i<n;i++){
int u,v;
cin>>u>>v;
c[u].push_back(v); // vector邻接表存树
c[v].push_back(u); // 双向边
}
- dfs 搜树：
void dfs(int u,int fa) // 两个参数：u是当前节点，fa是当前节点的父亲节点
{
for(auto v:c[u]){ // 遍历与当前节点相连的节点，存在vector里
if(fa!=v){ // 当下一个节点不是当前节点的父亲节点就往下搜
dfs(v,u); // v是下一个节点，u是下一个节点的父亲节点
}
}
}
dfs(1,0); // 从根节点出发搜（这里默认1号节点为根节点）
注：dfs 函数需要另外传进去当前节点的父亲节点是因为防止节点的重复搜索。
- dfs 求树的深度：
void dfs(int u,int fa) // 两个参数：u是当前节点，fa是当前节点的父亲节点
{
d[u]=d[fa]+1; // 当前节点u的深度就是父亲节点深度fa + 1，d数组维护深度
for(auto v:c[u]){
if(fa!=v){
dfs(v,u);
}
}
}
dfs(1,0); // 从根节点出发搜（这里默认1号节点为根节点）
二、bfs搜图 + 连通块
1、增广数组
在二维平面图中，我们需要找到连通块就需要往当前位置的上、下、左、右的四个位置移动，那么实现这个移动我们就需要先打表增广数组，里面记录的是移动的增广量：
int dx[4]={0,0,1,–1}; // 上下左右四个方位
int dy[4]={1,–1,0,0};
int dxx[8]={0,0,1,1,1,–1,–1,–1}; // 比上下左右多出了四个斜方位
int dyy[8]={1,–1,0,1,–1,0,1,–1};
// 调用四个方位
for(int i=0;i<4;i++){
int tx=x+dx[i];
int ty=y+dy[i];
cout<<tx<<' '<<ty<<'\\n';
}
// 调用八个方位
for(int i=0;i<8;i++){
int tx=x+dx[i];
int ty=y+dy[i];
cout<<tx<<' '<<ty<<'\\n';
}
2、bfs 搜索逻辑
伪代码：
int dx[4]={0,0,1,–1}; // x坐标上的增广量
int dy[4]={1,–1,0,0}; // y坐标上的增广量
void bfs()
{
// 声明队列，并且把起点放在队列里面
// 循环队列，取出队头，搜索上下左右四个位置是否符合条件。
if（符合条件） {
// 标记
// 把点放在队列里面
}
}
3、bfs 搜索连通块模板
一个
n
×
m
n×m
n×m 的方格图，一些格子被涂成了黑色，在方格图中被标为
1
1
1，白色格子标为
0
0
0，问有多少个四连通的黑色格子连通块。
四连通的黑色格子连通块指的是一片由黑色格子组成的区域，其中的每个黑色格子能通过四连通的走法（上下左右），只走黑色格子，到达该联通块中的其它黑色格子。
输入格式
第一行两个整数
n
,
m
n,m
n,m，表示一个
n
×
m
n×m
n×m 的方格图。
接下来
n
n
n 行，每行
m
m
m 个整数，分别为
1
1
1 或
0
0
0，表示这个格子是黑色还是白色。
输出格式
一个整数，表示图中黑色格子连通块的数量。
数据范围
1
≤
n
,
m
≤
100
1≤n,m≤100
1≤n,m≤100
输入样例：
3 3
1 1 1
0 1 0
1 0 1
输出样例：
3
参考代码：
void bfs(int x,int y)
{
queue<PII> q; // 初始化
q.push({x,y});
st[x][y]=true;
while(q.size()){
int x=q.front().first; // 取出队头（当前点）
int y=q.front().second;
q.pop();
for(int i=0;i<4;i++){ // 枚举四个坐标
int tx=x+dx[i];
int ty=y+dy[i];
if(tx>=1&&ty>=1&&tx<=n&&ty<=m&&g[tx][ty]==1&&!st[tx][ty]){
q.push({tx,ty}); // 符合条件就放进队列里面进行搜索
st[tx][ty]=true;
}
}
}
}
三、中等模拟题（字符串处理）
例题：L2-050 懂蛇语 分数 25
在《一年一度喜剧大赛》第二季中有一部作品叫《警察和我之蛇我其谁》，其中“毒蛇帮”内部用了一种加密语言，称为“蛇语”。蛇语的规则是，在说一句话
A
A
A 时，首先提取
A
A
A 的每个字的首字母，然后把整句话替换为另一句话
B
B
B，
B
B
B 中每个字的首字母与
A
A
A 中提取出的字母依次相同。例如二当家说“九点下班哈”，对应首字母缩写是 JDXBH，他们解释为实际想说的是“京东新百货”…… 本题就请你写一个蛇语的自动翻译工具，将输入的蛇语转换为实际要表达的句子。
输入格式：
输入第一行给出一个正整数
N
N
N（
≤
10
5
≤10^5
≤105），为蛇语词典中句子的个数。随后
N
N
N 行，每行用汉语拼音给出一句话。每句话由小写英文字母和空格组成，每个字的拼音由不超过
6
6
6 个小写英文字母组成，两个字的拼音之间用空格分隔。题目保证每句话总长度不超过
50
50
50 个字符，用回车结尾。注意：回车不算句中字符。 随后在一行中给出一个正整数
M
M
M（
≤
10
3
≤10^3
≤103），为查询次数。后面跟
M
M
M 行，每行用汉语拼音给出需要查询的一句话，格式同上。
输出格式：
对每一句查询，在一行中输出其对应的句子。如果句子不唯一，则按整句的字母序输出，句子间用 | 分隔。如果查不到，则将输入的句子原样输出。 注意：输出句子时，必须保持句中所有字符不变，包括空格。
输入样例：
8
yong yuan de shen
yong yuan de she
jing dong xin bai huo
she yu wo ye hui shuo yi dian dian
liang wei bu yao chong dong
yi dian dian
ni hui shuo she yu a
yong yuan de sha
7
jiu dian xia ban ha
shao ye wu ya he shui you dian duo
liu wan bu yao ci dao
ni hai shi su yan a
yao diao deng
sha ye ting bu jian
y y d s
输出样例：
jing dong xin bai huo
she yu wo ye hui shuo yi dian dian
liang wei bu yao chong dong
ni hui shuo she yu a
yi dian dian
sha ye ting bu jian
yong yuan de sha|yong yuan de she|yong yuan de shen
时间限制：400 ms
内存限制：64 MB
四、拓扑排序
啥是拓扑排序？（Kahn’s 算法）
- 一个有向图，如果图中有入度为 0 的点，就把这个点删掉，同时也删掉这个点所连的边。
- 一直进行上面出处理，如果所有点都能被删掉，则这个图可以进行拓扑排序。
比如说：
开始时，图是这样的状态，发现 A 的入度为 0，所以删除 A 和 A 上所连的边，结果如下图：
这时发现 B 的入度为 0，C 的入度为 0，所以删除 B 和 B 上所连的边、C 和 C 上所连的边，结果如下图：
这时发现发现 D 的入度为 0，所以删除 D 和 D 上所连的边(如果有就删)，结果如下图：
这时整个图被删除干净，所有能进行拓扑排序。
拓扑排序解题思路：
- 首先记录各个点的入度
- 然后将入度为 0 的点放入队列
- 将队列里的点依次出队列，然后找出所有出队列这个点发出的边，删除边，同事边的另一侧的点的入度 -1。
- 如果所有点都进过队列，则可以拓扑排序，输出所有顶点。否则输出-1，代表不可以进行拓扑排序。
例题：最短工期
一个项目由若干个任务组成，任务之间有先后依赖顺序。项目经理需要设置一系列里程碑，在每个里程碑节点处检查任务的完成情况，并启动后续的任务。现给定一个项目中各个任务之间的关系，请你计算出这个项目的最早完工时间。
输入格式：
首先第一行给出两个正整数：项目里程碑的数量
N
N
N（
≤
100
≤100
≤100）和任务总数
M
M
M。这里的里程碑从
0
0
0 到
N
−
1
N−1
N−1 编号。随后
M
M
M 行，每行给出一项任务的描述，格式为“任务起始里程碑 任务结束里程碑 工作时长”，三个数字均为非负整数，以空格分隔。
输出格式：
如果整个项目的安排是合理可行的，在一行中输出最早完工时间；否则输出 Impossible。
输入样例 1：
9 12
0 1 6
0 2 4
0 3 5
1 4 1
2 4 1
3 5 2
5 4 0
4 6 9
4 7 7
5 7 4
6 8 2
7 8 4
输出样例 1：
18
输入样例 2：
4 5
0 1 1
0 2 2
2 1 3
1 3 4
3 2 5
输出样例 2：
Impossible
参考代码：
vector<PII> c[N];
int d[N],s[N];
int T,n,m,k;
void solve()
{
cin>>n>>m;
for(int i=1;i<=m;i++){
int u,v,w;
cin>>u>>v>>w;
c[u].push_back({v,w}); // 存边（有边权）
d[v]++;
}
int cnt=0;
queue<int> q;
for(int i=0;i<n;i++){ // 先把入度为0的点放进队列
if(!d[i]){
cnt++; // 统计拓扑序的点数
q.push(i);
}
}
while(q.size()){ // 进行队列去点去边操作
auto u=q.front();
q.pop();
for(auto p:c[u]){ // 遍历当前点u的下一个点v
int v=p.x;
int w=p.y;
d[v]—; // 删边入度–
s[v]=max(s[v],s[u]+w); // 更新最大完工时间
if(!d[v]){ // 入度为0的点加进队列
q.push(v);
cnt++;
}
}
}
if(cnt!=n){ // 不满足拓扑序
cout<<"Impossible"<<'\\n';
return;
}
int mx=0;
for(int i=0;i<n;i++) mx=max(mx,s[i]); // 找最大时间
cout<<mx<<'\\n';
}
