U175308 队列、栈、链表、递归、有向无环图、拓扑序、 Dijsktra、 二叉树【笔记】
题目背景
#
### ·$queue$（队列）
·$push$——在队尾加入一个元素
·$pop$——在队头弹出一个元素
·$front$——返回队头元素，但不删除
·$back$——返回队尾元素，但不删除
·$empty$——如果队为空返回true，否则返回false
·$size$——返回队内元素的数量
### ·$stack$（栈）
·相比队列，无法获取栈底元素，获取栈顶元素改为$top()$即可
·——————————————————
·**链表$ list list1$（创建）**
·**头文件：$$**
·**创建一个链表的迭代器：$list ::iterator$ 迭代器名**
·头部添加一个元素t：$push$$_$$front(t)$
·尾部添加一个元素t：$push$$_$$back(t)$
·删除第一个元素：$pop$$_$$front()$
·删除最后一个元素：$pop$$_$$back()$
·返回指向第一个元素的迭代器：$begin()$
·返回指向末尾元素的迭代器：$end()$
·插入一个元素到$list$中：$insert()$
·删除一个元素：$erase()$
·从$list$删除元素：$remove()$
·返回$list$的元素个数：$size()$
·返回$list$是否为空，空为$true：empty()$
·删除所有元素：$clear()$
·——————————————————
### ·从前往后输出链表元素
```cpp
list 链表名;
list ::iterator 迭代器名 = 链表名.begin();
for (迭代器名 = 链表名.begin();迭代器名 != 链表名.end();迭代器名++){
printf("%d ",*迭代器名);
}
```
### ·添加
```cpp
链表名.insert(迭代器名,要添加的元素)
（若迭代器指向开头，插入开头，若指向末尾，插入末尾）
```
### ·删除（$erase$）
```cpp
链表名.erase(迭代器名)
（若迭代器指向开头，删除开头，若指向末尾，删除末尾）
```
### ·删除（$remove$）
```cpp
链表名.remove(要删除的元素t)
（删除链表中所有为t的元素）
```
·——————————————————
### ·递归
·**定义**：在函数运行的过程中自己调用自己。
·**条件**：
·$1、$递归在运行中必须要有退出条件或者有运行条件。
也就是递归的边界。
·$2、$递归在每次调用自己的时候都必须要靠近边界。
---
题目描述
# $★$
### 有向无环图（$DAG$）
·**有向**图。
·**无**环。
·重边：两点之间有多条边连接（大于或等于$2$）。
·自环：一条边的起点终点是一个点。
**有向无环图常常用来表示物体之间的依赖关系。**
$G$：图的简称。
$V$：点的集合。
$E$：边的集合。
设$G =（V，E）$是一个有向无环图且$|V| = n$。设$v_1,v_2,……v_n$是图上点的一个排列，若此排列满足：对于图$G$上每一有向边$（u，v）$都有$u$排在$v$之前，则称$v_1$，$v_2$，……$v_n$是图$G$上点的**一个拓扑序**。$（topological ordering）$。一般来说**拓扑序不唯一**。通常把求有向无环图的点的拓扑序称为**对有向无环图进行拓扑排序。**
## 图的性质
· **$★$无向图中，顶点的度的和等于边数的$2$倍。**
·**无向图中，度为奇数的顶点的数量一定是个偶数！**
·**有向图中，顶点的出度的和等于顶点的入度的和等于边数。**
---
## 图的概念
### 连通性
**首先**，它是这个无向图的一个连通子图 。**（保证连通）**
**其次**，他不是这个无向图的其他连通子图的子图 。**（保证极大）**
---
### 一些特殊的图
·**完全图：** 每对顶点间都有边的无向图
·**二分图：** 每条边的两个顶点分别来自有顶点集合$V$划分得到的两个子集$V_1、V_2$的无向图 。
---
### 拓扑序的性质
从点$u$可以到达的点一定排在$u$之后。
### 有向图
以点$u$为端点的边分成两类：$u$的出边和$u$的入边。
类似地定义$u$入度和$u$的出度。
### 车站分级
建模：有向无环图。
目标：有向无环图上最长路径的长度。
递推：设$f(u)$为从点$u$出发的最长路径的长度。$f(u) = 1 + max(v)$是$u$的邻点
边界条件：若$u$的出度为零，$f(u)=0$。
复杂度分析：朴素建图方式有$500×500×1000$
对每一个带编号的函数算出它的最简形式。
$M$
$(p_1，v_1)，(p_2，v_2)，……，(p_k，v_k)$
对单个加的效果汇总：
$Q$次函数调用里，对于一个特定函数的所有调用的效果里，加的一部分前面的系数。
---
## 最短路
**最短路径的性质：负边与负回路。**
---
## $Dijsktra$算法流程
**条件：没有负边**。$★$
1、 存图，初始化$d[ ]$，起点为$0$，其余为$inf$。
2、 选择$d[ ]$值最小**且**未被标记红色的点$x$，确定$d[x]$。
3、 标记$x$为红色，通过$x$**松弛**邻接点。
4、 重复$2$直到**没有可选的点**。
---
## [题目传送门](https://www.luogu.com.cn/problem/P4779)
## 代码
```cpp
#include
using namespace std;
// 相当于 pair 这个类型起个外号 p，在这个程序里写 p，就会认为是 pair
typedef pair p;
const int N = 1e5 + 10;
struct node {
int v, w;
};
vector G[N]; // 邻接表存图
int n, m, s; // 顶点数，边数，起点
int d[N]; // d[i]：起点到顶点 i 的最短路径
bool vis[N]; // 顶点是否已经确定从起点开始的最短路径
void Dijkstra(int s) {
// 初始化
memset(d, 0x3f, sizeof d);
priority_queue q; // 存的是（最短路径，顶点）
q.push({0, s}); // 起点入队
d[s] = 0; // 起点到起点的距离是 0
while(!q.empty()) {
p t = q.top();
q.pop();
// pair 是一个结构体，第一个成员 first，第二个成员叫 second
int u = t.second; // u 是我们选中的最短路径的顶点（结构体成员的访问）
if(vis[u]) continue; // u 如果顶点 u 已经确定了最短路径，跳过
vis[u] = true; // u 确定了最短路径
for(int i = 0; i < G[u].size(); i++) { // 找到 u 的所有邻居
int v = G[u][i].v, w = G[u][i].w;
if(!vis[v] && d[u] + w < d[v]) { // v 经过 u 过来的路径更短
d[v] = d[u] + w; // 松弛 v 的最短路径
q.push({d[v], v});
}
}
}
}
int main(){
cin >> n >> m >> s;
for(int i = 1; i v
cin >> u >> v >> w;
G[u].push_back({v, w});
}
Dijkstra(s); // 以 s 为起点到所有顶点的最短路径
for(int i = 1; i T;
while(T--) {
init(); // 初始化函数
cin >> n >> m;
for(int i = 1; i v
cin >> u >> v >> w;
G[u].push_back({v, w}); // u--w-->v
if(w >= 0) G[v].push_back({u, w}); // v--w-->u
}
if(SPFA(1)) cout > k;
for (int i = 1;i > u >> v >> w;
dp[u][v] = w;
}
Floyd();
for (int i = 1;i > u >> v;
if (dp[u][v] < 0x3f3f3f3f) cout
输入格式
#
## 欧拉回路
**欧拉回路**：图$G$中的一个**包含所有边**的**简单回路**成为欧拉回路。
**欧拉路径**：图$G$中的一个**包含所有边**的**简单路径**成为欧拉路径。
---
## 欧拉回路的性质
- 欧拉回路**一定包含**欧拉路径$！$$！$$！$
### - $★$除了不同的起点和终点外，都要求有成对的出入边。
---
### 拓展：汉密尔顿$（Hamilton）$回路
---
---
## 拓扑排序：$Kahn's$ 算法
$1、$**初始化一个队列**来暂存入度为$0$的点。
$2、$**遍历整个图**，将其中入度为$0$的顶点**入队**。
$3、$当队**不空**的时候：
$（1）$**取出队首元素**，将其插入当前的到的拓扑序列的末端。
$（2）$遍历它的**每条出边**，删除，如果对应的终点的入度为$0$，则**将它入队**。
$4、$返回得到的**拓扑序列**。**(如果长度不够，说明有环)** $★$
---
## 代码
```cpp
#include
using namespace std;
const int N = 1e6 + 10;
vector G[N]; // 存图
vector ans; // 存拓扑排序
int n, m; // 顶点数，边数
int inD[N]; // 每个顶点的入度
void TopoSort() {
queue q;
for(int i = 1; i v 这条边）
if(inD[v] == 0) q.push(v);
}
}
}
int main() {
cin >> n >> m;
for(int i = 1; i v
cin >> u >> v;
G[u].push_back(v);
inD[v]++; // v 的入度加 1
}
TopoSort(); // 拓扑排序
if(ans.size() < n) cout n >> m;
for(int i = 1; i v
cin >> u >> v;
G[u].push_back(v);
outD[u]++; // u 的出度加 1
inD[v]++; // v 的入度加 1
}
TopoSort(); // 拓扑排序（目的是求出以每个点为终点的路径条数）
int ans = 0; // 最大食物链的数量（总的有多少条食物链，多少条路径）
for(int i = 1; i
输出格式
无
说明/提示
想要通过么？
输出“hello 敢问高姓大名”就不能通过了！