搜索与图论算法总结
一、DFS
二、BFS
三、树与图的深度优先遍历
3.1、树的重心
四、树与图的广度优先遍历
4.1、图中点的层次
五、拓扑排序
5.1、有向图的拓扑序列
六、Dijkstra
6.1、Dijkstra求最短路1
6.2、Dijkstra求最短路2
七、bellman-ford
7.1、有边数限制的最短路
八、spfa
九、Floyd
9.1、Floyd求最短路
十、Prim
10.1、Prim算法求最小生成树
十一、Kruskal
11.1、Kruskal算法求最小生成树
十二、染色法判定二分图
12.1、染色法判定二分图
匈牙利算法
————————————————————————————————————————————————————————————————————————
///*
// * @Author: YMYS
// * @Date: 2025-04-09 21:28:22
// * @LastEditTime: 2025-04-09 21:46:42
// * @FilePath: \VScode-C&C++-Coding\Acwing\算法基础课\3.第三章\搜索与图论总结.cpp
// * @URL:
// * @Description: 搜索与图论总结
// *
// */
一、DFS
1.1、排列数字
///////////////////////////////////////////////////////省赛部分//////////////////////////////////////////////////
///*
// 一、dfs
//*/
////1.1、排列数字
////https://www.acwing.com/problem/content/844/
//#include<bits/stdc++.h>
//
//#define int long long
//#define err cout << "error" << endl
//
//using namespace std;
//
//const int N = 10;
//
//// int T;
//// void solve(){
//
//// }
//
//int n;
//bool p[N];
//vector<int> vc;
//
//void dfs(int x,int u){
// if(u==n){
// for(auto xx : vc) cout<<xx<<" ";
// cout<<endl;
// return;
// }
//
// for(int i=1;i<=n;i++){
// if(!p[i]){
// p[i] = true;
// vc.push_back(i);
// dfs(i,u+1);
// p[i] = false;
// vc.pop_back();
// }
// }
//}
//
//signed main()
//{
//#ifdef ABC
// freopen("D:/daily_Coding/VScode-C&C++-Coding/in.in", "r", stdin);
// freopen("D:/daily_Coding/VScode-C&C++-Coding/out.out", "w", stdout);
//#endif
// std::ios::sync_with_stdio(false);cin.tie(0); cout.tie(0);
//
// // cin>>T;
// // while(T--){
// // solve();
// // }
// cin>>n;
// for(int i=1;i<=n;i++){
// p[i] = true;
// vc.push_back(i);
// dfs(i,1);
// vc.pop_back();
// p[i] = false;
// }
//
//
//
//
// return 0;
//}
1.2、n-皇后问题
// //1.2、n-皇后问题
// //https://www.acwing.com/problem/content/845/
// // 注意！！！什么时候适用于使用Dfs？当题目中是要用类似一位一位全排列的时候，就用dfs，模板套路一样
// #include <bits/stdc++.h>
// using namespace std;
// const int N = 20; // 因为对角线数组的数值范围，所以改成了2N
// int n;
// char g[N][N]; // 存的是整个二维矩阵
// bool col[N]; // 表示列的，eg. col[i]表示第i列是否已经存在皇后
// bool dg[N]; // 下标是对角线的，eg. dg[i]表示截距是i的对角线是否已经存在皇后
// bool udg[N]; // 下标是反对角线的，eg. udg[i]表示截距是i的反对角线是否已经存在皇后
// // x表示第几行，y表示第几列
// // 我们发现该题的性质是不能在同一行下棋，因此我们没有必要按二维在一个点一个点的去遍历。
// //每次dfs行就可以，因为假如我们遍历了第i行第j列，就不用在遍历第i行的其他点了
// void dfs(int x)
// {
// // x==n，表示整个二维数组已经遍历完了，我们需要从头开始把他的每一行的数据输出出来
// // 矩阵中的数据一行一行输出
// if (x == n)
// {
// for (int i = 0; i < n; i++)
// {
// cout << g[i] << endl;
// }
// cout << endl;
// return;
// }
// for (int y = 0; y < n; y++)
// // 1、问：下面两个参数为社么是x+y与y-x+n?
// // 答：已知在该题的二维矩阵中存在y=x+b、y=-x+b，两种形式的直线。
// // 他们的截距表示为：b=x+y、b=y-x两种
// // 但是y-x有可能为负，所以我们加个位移量n，也就是y-x+n确保是正数
// // 所以，x+y与y-x+n
// // 2、问：这个if是做什么的？
// // 答：剪枝（对于不满足要求的点，不再继续往下搜索）
// //3、为什么这里的截距不能对n取mol。【即：(y-x+n)%n】
// // 答：因为我们在这里x+y的范围最大值就已经是20了，所以后面(y-x)的范围是(-10, 10)我们向右平移10也无伤大雅
// if (!col[y] && !udg[x + y] && !dg[y - x + n])
// {
// g[x][y] = 'Q';
// col[y] = udg[x + y] = dg[y - x + n] = true;
// dfs(x + 1);
// // 恢复现场
// col[y] = udg[x + y] = dg[y - x + n] = false;
// g[x][y] = '.';
// }
// }
// signed main()
// {
// #ifdef ABC
// freopen("D:\\daily_Coding\\VScode-C&C++-Coding\\in.in", "r", stdin);
// freopen("D:\\daily_Coding\\VScode-C&C++-Coding\\out.out", "w", stdout);
// #endif
// ios::sync_with_stdio(false);
// cin.tie(0);
// cout.tie(0);
// cin >> n;
// // 将整个二维矩阵初始化为'.'
// for (int i = 0; i < n; i++)
// for (int j = 0; j < n; j++)
// g[i][j] = '.';
// // 开始dfs
// dfs(0);
// return 0;
// }
// //1.2、n-皇后问题
// #include<bits/stdc++.h>
// #define int long long
// #define err cout << "error" << endl
// using namespace std;
// const int N = 20;
// // int T;
// // void solve(){
// // }
// int n;
// char c[N][N];
// bool p[N][N];
// bool l[N];//列
// bool a[N];//对角线(y=x+b --> b=y-x --> y-x+n)
// bool b[N];//反对角线(y=-x+b --> b=y+x)
// void dfs(int x){
// if(x==n){
// for(int i=0;i<n;i++) cout<<c[i]<<endl;
// cout<<endl;
// }
// //(x, y)
// for(int y=0;y<n;y++){
// if(a[y-x+n] || b[y+x] || l[y] || p[x][y]) continue;
// p[x][y] = true;
// a[y-x+n] = true;
// b[y+x] = true;
// l[y] = true;
// c[x][y] = 'Q';
// dfs(x+1);
// c[x][y] = '.';
// l[y] = false;
// b[y+x] = false;
// a[y-x+n] = false;
// p[x][y] = false;
// }
// }
// signed main()
// {
// #ifdef ABC
// freopen("D:/daily_Coding/VScode-C&C++-Coding/in.in", "r", stdin);
// freopen("D:/daily_Coding/VScode-C&C++-Coding/out.out", "w", stdout);
// #endif
// std::ios::sync_with_stdio(false);cin.tie(0); cout.tie(0);
// // cin>>T;
// // while(T--){
// // solve();
// // }
// cin>>n;
// for(int i=0;i<n;i++){
// for(int j=0;j<n;j++){
// c[i][j] = '.';
// }
// }
// dfs(0);
// return 0;
// }
二、bfs
2.1、走迷宫
// /*
// 二、bfs
// */
// //2.1、走迷宫
// //https://www.acwing.com/problem/content/846/
// //dfs算法解决，TLE
// #include<bits/stdc++.h>
// #define int long long
// #define err cout << "error" << endl
// using namespace std;
// const int N = 110;
// // int T;
// // void solve(){
// // }
// int n,m;
// int p[N][N];
// bool k[N][N];
// int dx[4] = {0, 1, 0, -1};
// int dy[4] = {1, 0, -1, 0};
// int res;
// int ans = 1e9;
// void dfs(int x,int y){
// if(x==n && y==m){
// ans = min(ans, res);
// // cout << res << endl;
// }
// for(int i=0;i<4;i++){
// int xx = x + dx[i];
// int yy = y + dy[i];
// if(xx<1 || xx>n || yy<1 || yy>m) continue;
// if(k[xx][yy]) continue;
// if(p[xx][yy]) continue;
// k[xx][yy] = true;
// res++;
// dfs(xx, yy);
// res--;
// k[xx][yy] = false;
// }
// }
// signed main()
// {
// #ifdef ABC
// freopen("D:/daily_Coding/VScode-C&C++-Coding/in.in", "r", stdin);
// freopen("D:/daily_Coding/VScode-C&C++-Coding/out.out", "w", stdout);
// #endif
// std::ios::sync_with_stdio(false);cin.tie(0); cout.tie(0);
// // cin>>T;
// // while(T--){
// // solve();
// // }
// cin>>n>>m;
// for(int i=1;i<=n;i++){
// for(int j=1;j<=m;j++){
// cin>>p[i][j];
// }
// }
// k[1][1] = true;
// dfs(1,1);
// cout<<ans<<endl;
// return 0;
// }
// //2.1、走迷宫
// //bfs算法解决
// //推荐的题解：https://www.acwing.com/solution/content/36520/
// //原题链接：https://www.acwing.com/problem/content/846/
// #include<bits/stdc++.h>
// #define int long long
// #define err cout << "error" << endl
// using namespace std;
// typedef pair<int, int> PII;
// const int N = 110;
// // int T;
// // void solve(){
// // }
// int n,m;
// int p[N][N];
// int w[N][N];
// queue<PII> pii;
// void bfs(){
// int dx[4] = {0,0,1,-1};
// int dy[4] = {1,-1,0,0};
// while (!pii.empty())
// {
// PII pi = pii.front();
// pii.pop();
// p[pi.first][pi.second] = 1;
// for(int i=0;i<4;i++){
// int xx = pi.first + dx[i];
// int yy = pi.second + dy[i];
// if(!p[xx][yy]){
// pii.push({xx, yy});
// p[xx][yy] = 1;
// w[xx][yy] = w[pi.first][pi.second] + 1;
// }
// }
// }
// }
// signed main()
// {
// #ifdef ABC
// freopen("D:/daily_Coding/VScode-C&C++-Coding/in.in", "r", stdin);
// freopen("D:/daily_Coding/VScode-C&C++-Coding/out.out", "w", stdout);
// #endif
// std::ios::sync_with_stdio(false);cin.tie(0); cout.tie(0);
// // cin>>T;
// // while(T--){
// // solve();
// // }
// memset(p , 1, sizeof p);
// cin>>n>>m;
// for(int i=1;i<=n;i++){
// for(int j=1;j<=m;j++){
// cin>>p[i][j];
// }
// }
// pii.push({1,1});
// w[1][1] = 0;
// bfs();
// cout << w[n][m] <<endl;
// return 0;
// }
2.2、八数码
// //2.2、八数码
// //https://www.acwing.com/problem/content/847/
// /*
// 思路：常见的bfs模式套路，在queue队列中不断加入状态，直到把所有的状态都遍历完。
// *** 这里的思路是把二维的char数组，转化为一维的string，判断其是否等于终点string（因为终点stirng是固定的"12345678x"）
// //
// //注意！！！什么时候适用于使用Bfs？当题目中提出一圈一圈的遍历点的时候就用bfs，模板套路一样
// //
// */
// #include <iostream>
// #include <algorithm>
// #include <queue>
// #include <unordered_map>//哈希表
// using namespace std;
// using namespace __gnu_cxx;
// int bfs(string start)
// {
// //定义目标状态
// string end = "12345678x";
// //定义队列和dist数组
// queue<string> q;
// unordered_map<string, int> d;
// //初始化队列和d（dist）数组
// q.push(start);
// d[start] = 0;
// //转移方式(下、上、右、左)
// int dx[4] = {1, -1, 0, 0}, dy[4] = {0, 0, 1, -1};
// while(q.size())
// {
// auto t = q.front();
// q.pop();
// //记录当前状态的距离，如果是最终状态则返回距离
// int distance = d[t];
// if(t == end) return distance;
// //查询x在字符串t中的下标，然后转换为在矩阵中的坐标
// int k = t.find('x');
// int x = k / 3, y = k % 3;
// //上下左右遍历一下（不管是不是对的数，都会进行遍历，去加入queue。如果是第一次遍历，则记录对应距离，入队）
// for(int i = 0; i < 4; i++)
// {
// //求转移后x的坐标
// int a = x + dx[i], b = y + dy[i];
// //表示当前坐标没有越界
// if(a >= 0 && a < 3 && b >= 0 && b < 3)
// {
// //转移x
// swap(t[k], t[a * 3 + b]);
// //如果当前状态是第一次遍历，记录距离，入队
// if(!d.count(t))//保证队中没有重复元素
// {
// d.insert({t, distance+1});//d[string][int]
// //也可以这样【d[t] = distance + 1】
// q.push(t);
// }
// //还原状态，为下一种转换情况做准备【这行代码只是作用于上下左右四种情况，对while的每一层循环无用】
// swap(t[k], t[a * 3 + b]);
// }
// }
// }
// //退出while循环以后，表示每一种情况都遍历过了。但是并没有从上面中的return退出去，说明不存在解决方案
// //无法转换到目标状态，返回-1（找到的话，会从上面的return出去）
// return -1;
// }
// int main()
// {
// #ifdef ABC
// freopen("D:\\daily_Coding\\VScode-C&C++-Coding\\in.in", "r", stdin);
// freopen("D:\\daily_Coding\\VScode-C&C++-Coding\\out.out", "w", stdout);
// #endif
// ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
// char c;
// string start;
// //为什么这里要用c坐中间件？
// //答：因为给的数据之间有空格，不然的话string start这个字符串之间会有空格存在
// for(int i = 0; i < 9; i++)
// {
// cin >> c;
// start += c;
// }
// cout << bfs(start) << endl;
// return 0;
// }
三、树与图的深度优先遍历
3.1、树的重心
// /*
// 三、树与图的深度优先遍历
// */
// //3.1、树的重心
// //https://www.acwing.com/problem/content/848/
// //树的重心
// #include<bits/stdc++.h>
// using namespace std;
// const int N = 1e5 + 10; //数据范围是10的5次方
// const int M = 2 * N; //以有向图的格式存储无向图，所以每个节点至多对应2n-2条边
// int h[N]; //邻接表存储树，有n个节点，所以需要n个队列头节点
// int e[M]; //存储边，e[i]表示的是以i结尾的边
// int ne[M]; //存储列表的边的next值
// int idx; //单链表指针
// int n; //题目所给的输入，n个节点
// int ans = N; // 因为是求每个节点删除后剩余连通块节点最大值的最小值, 所以 ans 需要初始化为 N
// bool st[N]; //记录节点是否被访问过，访问过则标记为true
// //a所对应的单链表中插入b a作为根
// void add(int a, int b) {
// e[idx] = b, ne[idx] = h[a], h[a] = idx++;
// }
// // 树的 dfs 框架
// /*
// void dfs(int u){
// st[u]=true; // 标记一下，记录为已经被搜索过了，下面进行搜索过程
// //非零值会被视为 true，而零值会被视为 false。因此，if(-1) 和 if(1) 都会被执行
// for(int i=h[u];i!=-1;i=ne[i]){
// int j=e[i];
// if(!st[j]) {
// dfs(j);
// }
// }
// }
// */
// /*
// 主要思想：我们刚开始将每个顶点的sum，也就是最大连通子图个数都初始化为1，也就是只包含他自己目前这一个点。
// 然后我们使用dfs递归，使得整个树的遍历是从小到大开始回溯的，然后慢慢的从树的尾部逐渐计算最大sum，每次回溯到上一个父节点时，加上父节点相邻的子结点的sum，就是这个顶点的所有子树结点
// */
// //返回以u为根的子树中节点的个数，包括u节点
// int dfs(int u) {
// int res = 0; //存储 删掉某个节点之后，最大的连通子图节点数
// st[u] = true; //标记当前访问的u节点
// int sum = 1; // sum 记录 u 节点下(包括 u 节点)在内的所有节点的个数, 一开始只有 u 节点, 所以初始值 = 1
// //访问u的每个子节点
// for (int i = h[u]; i != -1; i = ne[i]) {
// int j = e[i];
// //因为每个节点的编号都是不一样的，所以 用编号为下标 来标记是否被访问过
// if (!st[j]) {
// int s = dfs(j); // j节点的单棵子树节点数
// res = max(res, s); // 记录最大联通子图的节点数
// sum += s; //以j为根的树 的节点数
// }
// }
// res = max(res, n - sum); // 上面哪个res是遍历以u为根的子树的最大连通子图节点数，这一行的代码是求反，意思就是将整个树减去所有以u为根的子树，即剩下的部分，去进行判断
// // 因为是求每个节点删除后剩余连通块节点最大值的最小值, 所以 ans 需要初始化为 N
// ans = min(res, ans); //遍历过的假设重心中，最小的最大联通子图的 节点数
// return sum;//返回以u为根的子树的所有结点个数
// }
// int main() {
// #ifdef ABC
// freopen("D:\\daily_Coding\\VScode-C&C++-Coding\\in.in", "r", stdin);
// freopen("D:\\daily_Coding\\VScode-C&C++-Coding\\out.out", "w", stdout);
// #endif
// ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
// cin >> n; //表示树的结点数
// memset(h, -1, sizeof h); //初始化h数组 -1表示尾节点
// // 题目接下来会输入，n-1行数据，
// // 树中是不存在环的，对于有n个节点的树，必定是n-1条边
// for (int i = 0; i < n - 1; i++) {
// int a, b;
// cin >> a >> b;
// add(a, b), add(b, a); //无向图
// }
// dfs(1); //可以任意选定一个节点开始 u<=n
// cout << ans << endl;
// return 0;
// }
// //自己敲的
// /*
// #pragma GCC target ("avx")
// #pragma GCC optimize(3,"Ofast","inline")
// #include<bits/stdc++.h>
// #define int long long
// #define endl '\n'
// using namespace std;
// using namespace __gnu_cxx;
// using ll = long long;
// typedef pair<int, int> PII;
// const int N = 1e5+10, M = 2*N;
// //邻接表的存储结构
// int h[N];//头节点的组成的数组
// int e[M];//存的是所有的点的下标
// int ne[M];//存的是头结点所属的单链表
// bool st[N];//判断是否遍历过
// int idx;//标记
// int ans = N;//答案，最大值中的最小值
// int n;//结点数
// void add(int a,int b){
// e[idx] = b;
// ne[idx] = h[a];
// h[a] = idx++;
// }
// int dfs(int u){
// st[u] = true;
// int sum = 1;//当前以u为根的子树的所有结点个数
// int res = 0;//计算以u为中心的最大连通子树的所有结点个数
// for(int i=h[u]; i != -1; i=ne[i]){
// int j = e[i];
// if(!st[j]){
// int r = dfs(j);
// res = max(res, r);
// sum += r;
// }
// }
// res = max(res, n-sum);
// ans = min(ans, res);//求最大值中的最小值
// return sum;
// }
// signed main()
// {
// #ifdef ABC
// freopen("D:\\daily_Coding\\VScode-C&C++-Coding\\in.in", "r", stdin);
// freopen("D:\\daily_Coding\\VScode-C&C++-Coding\\out.out", "w", stdout);
// #endif
// ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
// cin>>n;
// //一定要记得初始化头结点数组为-1
// memset(h, -1, sizeof h);
// for(int i=0;i<n-1;i++){
// int a,b;
// cin>>a>>b;
// add(a,b), add(b,a);//树是一种无向图，所以加上有向边(a,b)、(b,a)
// }
// dfs(1);
// cout<<ans<<endl;
// return 0;
// }
// */
四、树与图的广度优先遍历
4.1、图中点的层次
// /*
// 四、树与图的广度优先遍历
// */
// //4.1、图中点的层次
// //https://www.acwing.com/problem/content/849/
// //847.图中点的层次
// #include<bits/stdc++.h> // 包含标准库的头文件
// using namespace std; // 使用标准命名空间
// const int N = 1e5+10; // 定义全局常量 N
// //e[]、ne[]数组存的都是边
// //注意：我们这里的h[]、e[]、ne[]、st[]的下标都是每个结点的编号。h、ne存的是几号顶点，比如顶点1到顶点2
// int n,m,h[N],e[N*2],ne[N*2],idx; // 定义全局变量 n（节点数量）、m（边的数量）、h[]（邻接表头数组）、e[]（邻接表存储边的数组）、ne[]（邻接表存储边的下一个节点的数组）、idx（边的数量计数器）
// bool st[N]; // 定义全局布尔数组 st[]，用于标记节点是否已经访问过
// void add(int a,int b) { // 定义函数 add，用于向邻接表中添加边
// e[idx] = b; // 将节点 b 添加到邻接表中
// ne[idx] = h[a]; // 更新邻接表中节点 a 的下一个节点为原来的头节点
// h[a] = idx; // 更新节点 a 的头节点为当前添加的边的索引
// idx++;
// }
// int bfs(){ // 定义广度优先搜索函数 bfs
// queue<pair<int,int>> q; // 队列中存储每个节点的编号和到达该节点的最短距离
// q.push({1,0}); // 将起始节点 1 和到达该节点的距离 0 入队
// st[1] = true; // 标记起始节点 1 已经访问过
// while(q.size()) { // 当队列不为空时，执行循环
// auto u = q.front(); // 取出队首元素
// q.pop(); // 弹出队首元素
// int a = u.first, d = u.second; // 获取当前节点编号和到达该节点的距离
// st[a] = true; // 标记当前节点已经访问过
// if(a == n) return d; // 如果当前节点为目标节点 n，则返回到达该节点的距离。第一次遇到n就是最短的距离
// for(int i=h[a]; i; i=ne[i]) { // 遍历当前节点的邻接节点
// int j = e[i]; // 获取邻接节点编号
// if(!st[j]) { // 如果邻接节点未被访问过
// q.push({j,d+1}); // 将邻接节点和到达该节点的距离加一入队
// }
// }
// }
// return -1; // 如果无法到达目标节点 n，则返回 -1
// }
// int main() { // 主函数
// #ifdef ABC
// freopen("D:\\daily_Coding\\VScode-C&C++-Coding\\in.in", "r", stdin); // 输入重定向
// freopen("D:\\daily_Coding\\VScode-C&C++-Coding\\out.out", "w", stdout); // 输出重定向
// #endif
// ios::sync_with_stdio(false), cin.tie(0), cout.tie(0); // 关闭流同步，加快输入输出速度
// cin>>n>>m; // 输入节点数量 n 和边的数量 m
// int a,b;
// while(m--) { // 循环读入边的信息，并构建邻接表
// cin>>a>>b; // 输入边的起点和终点
// add(a,b); // 因为是有向边，所以只弄一个
// }
// cout<<bfs()<<endl; // 输出广度优先搜索得到的结果，即从节点 1 到节点 n 的最短距离
// return 0; // 返回 0，表示程序正常结束
// }
五、拓扑排序
5.1、有向图的拓扑序列
/*
五、拓扑排序
*/
// //5.1、有向图的拓扑序列
// //https://www.acwing.com/problem/content/850/
// //有向图的拓扑序列（注意：这个问题就是最好用BFS去做）
// #include<bits/stdc++.h>
// #define int long long
// #define endl '\n'
// #define x first
// #define y second
// using namespace std;
// using namespace __gnu_cxx;
// using ll = long long;
// typedef pair<int, int> PII;
// const int N = 1e5+10, M = 2*N;
// int n, m;
// int h[N];
// int e[M];
// int ne[M];
// int idx;
// int d[N];//表示所有点的入读的值
// vector<int> endx;//表示存的是最后的要输出的结果，存的是每一次从队列中弹出的值
// void add(int a,int b){
// e[idx] = b;
// ne[idx] = h[a];
// h[a] = idx++;
// }
// bool torpsort(){
// queue<int> p;//队列存的是入度为0的点
// for(int i=1;i<=n;i++)//这里的i表示点的值，我们不能用[0,n-1]，因为点的值是[1,n]的范围
// if(d[i] == 0) p.push(i);
// while (p.size())
// {
// auto x = p.front();
// p.pop();
// endx.push_back(x);
// for(int i=h[x]; i != -1 ; i = ne[i]){
// auto j = e[i];
// d[j]--;
// if(d[j] == 0) p.push(j);
// }
// }
// return endx.size() == n;
// }
// signed main()
// {
// #ifdef ABC
// freopen("D:\\daily_Coding\\VScode-C&C++-Coding\\in.in", "r", stdin);
// freopen("D:\\daily_Coding\\VScode-C&C++-Coding\\out.out", "w", stdout);
// #endif
// ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
// memset(h,-1,sizeof h);
// cin>>n>>m;
// for(int i=0;i<m;i++){
// int x,y;
// cin>>x>>y;
// add(x,y);
// d[y]++;
// }
// if(torpsort()){
// for(int i=0;i<endx.size();i++)
// cout<<endx[i]<<" ";
// }else cout<<"-1";
// cout<<endl;
// return 0;
// }
六、Dijkstra
6.1、朴素版迪杰斯特拉
// /*
// 六、Dijkstra
// */
// //6.1、朴素版迪杰斯特拉
// //https://www.acwing.com/problem/content/851/
// //Dijkstra求最短路I【朴素做法，适合于稠密图】
// /*
// 思路：时间复杂度：O(n^2)，适合于稠密图。注意：Dijkstra算法要求了必须是不存在负权边！
// */
// #include<bits/stdc++.h>
// #define int long long
// #define endl '\n'
// #define x first
// #define y second
// #define INF 0x3f3f3f3f3f3f3f3f//因为我们把int宏定义为了long long，所以极大值也需要改。int的极大值是四个3f3f3f3f，longlong是八个
// using namespace std;
// using namespace __gnu_cxx;
// using ll = long long;
// typedef pair<int, int> PII;
// const int N = 510;
// int n,m;//n是点数，m是边数。由题目数据得，该图为稠密图，所以应该用邻接矩阵存储
// int a[N][N];//a[i][j]存储的是有向边<i,j>的从i到j的边长
// int d[N];//d[i]表示从起点1到第i个点的最短距离
// bool st[N];//st[i]表示i是否是最短路
// int dijkstra(){
// memset(d,0x3f,sizeof d);
// d[1]=0;//源点到源点的距离为0
// for(int i=0;i<n;i++){//表示遍历n次，将n个点的最短路找到
// int t = -1;//这里的t表示为起始点的编号
// for(int j=1;j<=n;j++)//在所有点中，找到还未确定为是最短路径的，并且路径是这里面最短的点的编号
// if(!st[j] && (t==-1 || d[t] > d[j]))
// t = j;
// st[t] = true;
// //目前我们已经找到了一个紧挨着(所有已经确定是最短路的点)的点的编号t。
// //注意：这个t没有经过下面这个for循环时，还不是最短路。
// //我们需要遍历整个图的点，更新所有路径，使其变成是当前最短的路径
// for(int j = 1;j<=n;j++){
// d[j] = min(d[j], d[t]+a[t][j]);
// }
// }
// if(d[n] == INF) return -1;
// return d[n];
// }
// signed main()
// {
// #ifdef ABC
// freopen("D:\\daily_Coding\\VScode-C&C++-Coding\\in.in", "r", stdin);
// freopen("D:\\daily_Coding\\VScode-C&C++-Coding\\out.out", "w", stdout);
// #endif
// ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
// //注意：正常我们定义极大值，我们都是赋值0x3f3f3f3f
// //但是因为memset函数的特性，我们赋值0x3f即可
// memset(a,0x3f,sizeof a);//初始化每个点到点的边长为极大值
// cin>>n>>m;
// for(int i=0;i<m;i++){
// int x,y,z;
// cin>>x>>y>>z;
// a[x][y] = min(a[x][y],z);//注意有重边的情况，所以这里要取一下min
// }
// cout << dijkstra() << endl;
// return 0;
// }
6.2、优化版本的迪杰斯特拉
// //6.2、优化版本的迪杰斯特拉
// //https://www.acwing.com/problem/content/852/
// //Dijkstra求最短路II【堆优化做法，适合于稀疏图】。注意：Dijkstra算法要求了必须是不存在负权边！
// #include<bits/stdc++.h>
// #define int long long
// #define endl '\n'
// #define x first
// #define y second
// #define INF 0x3f3f3f3f3f3f3f3f
// using namespace std;
// using namespace __gnu_cxx;
// using ll = long long;
// typedef pair<int, int> PII;
// const int N = 150010;
// /*
// 编号指的是1~n 这些节点的号码，下标是节点在数组中存放的位置
// e[i]的值是编号，是下标为i节点的编号。
// ne[i]的值是下标，是下标为i的节点的next节点的下标。
// h[i]存储的是下标，是编号为i的节点的next节点的下标，比如编号为1的节点的下一个节点是4，那么我输出e[h[1]]就是编号为4的点。
// */
// int n,m;//n个点，m条边
// int h[N], e[N], ne[N], w[N], idx;//邻接表的存储方式
// int d[N];//存最短路径
// bool st[N];//判断是否已经是最短路径
// void add(int a,int b,int c){
// // 有重边也不要紧，假设1->2有权重为2和3的边，再遍历到点1的时候2号点的距离会更新两次放入堆中
// // 这样堆中会有很多冗余的点，但是在弹出的时候还是会弹出最小值2+x（x为之前确定的最短路径），
// // 并标记st为true，所以下一次弹出3+x会continue不会向下执行。
// e[idx] = b;
// w[idx] = c;
// ne[idx] = h[a];
// h[a] = idx++;
// }
// int dijkstra(){
// memset(d, INF , sizeof d);
// d[1]=0;
// priority_queue<PII, vector<PII>, greater<PII>> p;
// p.push({0,1});//前者是距离，后者是编号
// while (p.size())
// {
// auto xx = p.top();
// p.pop();
// int id = xx.y, distance = xx.x;
// if(st[id]) continue;
// st[id] = true;
// for(int i=h[id]; i != -1; i=ne[i]){
// int j = e[i];
// if(d[j] > distance + w[i]){
// d[j] = distance + w[i];
// p.push({d[j], j});
// }
// }
// }
// if(d[n] == INF) return -1;
// return d[n];
// }
// signed main()
// {
// #ifdef ABC
// freopen("D:\\daily_Coding\\VScode-C&C++-Coding\\in.in", "r", stdin);
// freopen("D:\\daily_Coding\\VScode-C&C++-Coding\\out.out", "w", stdout);
// #endif
// ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
// //memset(w,0x3f,sizeof w);//初始化权重为无穷大
// memset(h,-1,sizeof h);//初始化头节点为-1
// cin>>n>>m;
// while (m--)
// {
// int a,b,c;
// cin>>a>>b>>c;
// add(a,b,c);
// }
// cout<<dijkstra()<<endl;
// return 0;
// }
七、bellman-ford
7.1、有边数限制的最短路
// /*
// 七、bellman-ford
// */
// //7.1、有边数限制的最短路
// //https://www.acwing.com/problem/content/855/
// //853.有边数限制的最短路
// /*
// bellman_ford算法可以判断是否具有负环。
// spfa算法在各方面都比bellman_ford强大，
// 但是某些特殊的题，只有bellman_ford可以做，就是有最多行走边数的限制，如我们这道题
// 注意：图中可能 存在负权回路 。
// 思路：核心代码 ————> d[b] = min(d[b], md[a] + c)
// 只是我们需要处理一下串联的情况，解决代码如右 ————> memcpy(md, d , sizeof d)
// */
// #include<bits/stdc++.h>
// #define int long long
// #define INF 0x3f3f3f3f3f3f3f3f
// using namespace std;
// using ll = long long;
// const int N = 510, M = 10010;
// struct Edge {
// int a;
// int b;
// int w;
// } e[M];//保存点
// int dist[N];
// int back[N];//备份数组防止串联
// int n, m, k;//k代表最短路径最多包涵k条边
// int bellman_ford() {
// memset(dist, 0x3f, sizeof dist);
// dist[1] = 0;
// for (int i = 0; i < k; i++) {//只能执行k步，每次只处理一条边，一共执行k条边
// memcpy(back, dist, sizeof dist);//给back数组，赋值dist数组的所有值
// for (int j = 0; j < m; j++) {//遍历所有边
// int a = e[j].a, b = e[j].b, w = e[j].w;
// //更新源点到点b的距离是：源点到点a的距离+w 还是 源点到点b的距离
// dist[b] = min(dist[b], back[a] + w);
// //back这里存的是上一次遍历之前的值，在此层循环中，我们并没有更改back数组的任何一个值
// //所以并不会发生a更新后立马更新b, 这样避免了b发生一次性最短路径会多两条边出来
// }
// }
// return dist[n];
// }
// signed main()
// {
// #ifdef ABC
// freopen("D:\\daily_Coding\\VScode-C&C++-Coding\\in.in", "r", stdin);
// freopen("D:\\daily_Coding\\VScode-C&C++-Coding\\out.out", "w", stdout);
// #endif
// ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
// cin>>n>>m>>k;
// for (int i = 0; i < m; i++) {
// int a, b, w;
// cin>>a>>b>>w;
// e[i] = {a, b, w};
// }
// int t = bellman_ford();
// if(t > INT_MAX/2) cout<<"impossible"<<endl;//因为可能存在负权边，所以可能会使得边的初始化值INf变小一些
// else cout<<t<<endl;
// return 0;
// }
八、spfa
8.1、spfa求最短路
// /*
// 八、spfa
// */
// //8.1、spfa求最短路
// //https://www.acwing.com/problem/content/853/
// //851.spfa求最短路
// /*
// 思路：边权可能为负数，但一定不存在负权回路
// spfa算法就是对bellman_ford算法做优化。因为只有边<a,b>结点的a结点发生了变化，才会使得b结点的最短距离发生变化
// 所以我们对此进行优化，把发生变化的a点存入队列中。
// 也就是说，只有我更新过谁，我才拿这个点对其他点进行更新
// spfa可以判断是否具有负环
// */
// #include<bits/stdc++.h>
// #define int long long
// #define endl '\n'
// #define x first
// #define y second
// #define INF 0x3f3f3f3f3f3f3f3f
// using namespace std;
// using namespace __gnu_cxx;
// using ll = long long;
// typedef pair<int, int> PII;
// const int N = 150010;
// int n,m;//n个点，m条边
// int h[N], e[N], ne[N], w[N], idx;//邻接表的存储方式
// int d[N];//存最短路径
// bool st[N];//st[i]判断队列中是否已经存在下标为i的点
// void add(int a,int b,int c){
// e[idx] = b;
// w[idx] = c;
// ne[idx] = h[a];
// h[a] = idx++;
// }
// int spfa(){
// memset(d, INF, sizeof d);
// d[1]=0;
// queue<int> p;
// p.push(1);
// st[1] = true;
// while (p.size())
// {
// auto t = p.front();
// p.pop();
// st[t] = false;
// //更新与t邻接的边
// for(int i=h[t]; i!=-1; i=ne[i]){
// int j = e[i];
// if(d[j] > d[t] + w[i]){
// d[j] = d[t] + w[i];
// if(!st[j]){
// st[j] = true;
// p.push(j);
// }
// }
// }
// }
// return d[n];
// }
// signed main()
// {
// #ifdef ABC
// freopen("D:\\daily_Coding\\VScode-C&C++-Coding\\in.in", "r", stdin);
// freopen("D:\\daily_Coding\\VScode-C&C++-Coding\\out.out", "w", stdout);
// #endif
// ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
// memset(h,-1,sizeof h);//初始化头节点为-1
// cin>>n>>m;
// while (m--)
// {
// int a,b,c;
// cin>>a>>b>>c;
// add(a,b,c);
// }
// int t = spfa();
// if(t > LONG_LONG_MAX/2) cout<<"impossible"<<endl;//因为可能存在负权边，所以可能会使得边的初始化值INf变小一些
// else cout<<t<<endl;
// return 0;
// }
8.2、spfa判断负环
// //8.2、spfa判断负环
// //https://www.acwing.com/problem/content/854/
// //852.spfa判断是否存在负环
// /*
// 思路：边权可能为负数，但一定不存在负权回路
// spfa算法就是对bellman_ford算法做优化。因为只有边<a,b>结点的a结点发生了变化，才会使得b结点的最短距离发生变化
// 所以我们对此进行优化，把发生变化的a点存入队列中。
// 也就是说，只有我更新过谁，我才拿这个点对其他点进行更新
// spfa可以判断是否具有负环，思路：https://www.acwing.com/solution/content/6336/
// 《求负环的常用方法，基于SPFA，一般都用方法 2（该题也是用方法 2）》：
// 方法 1：统计每个点入队的次数，如果某个点入队n次，则说明存在负环
// 方法 2：统计当前每个点的最短路中所包含的边数，如果某点的最短路所包含的边数大于等于n，则也说明存在环
// */
// #include<bits/stdc++.h>
// #define int long long
// #define endl '\n'
// #define x first
// #define y second
// #define INF 0x3f3f3f3f3f3f3f3f
// using namespace std;
// using namespace __gnu_cxx;
// using ll = long long;
// typedef pair<int, int> PII;
// const int N = 2010, M = 10010;
// int n, m;//n个点，m条边
// int h[N], e[M], ne[M], w[M], idx;//邻接表的存储方式
// int d[N];//存最短路径
// bool st[N];//st[i]判断队列中是否已经存在下标为i的点
// int dnt[N];//dnt[i]表示源点到点i的最短距离的边数为多少
// void add(int a,int b,int c){
// e[idx] = b;
// w[idx] = c;
// ne[idx] = h[a];
// h[a] = idx++;
// }
// int spfa(){
// //不用再初始化 d[] 数组为INF了，因为我们判断的是有没有负环
// //memset(d, INF, sizeof d);
// //d[1]=0;
// queue<int> p;
// //不能只放1结点，因为负环不一定只从1结点开始。
// //我们需要把所有结点放入队列去循环遍历。
// //p.push(1);
// //st[1] = true;
// for(int i=1;i<=n;i++){
// p.push(i);
// st[i] = true;
// }
// while (p.size())
// {
// auto t = p.front();
// p.pop();
// st[t] = false;
// //更新与t邻接的边
// for(int i=h[t]; i!=-1; i=ne[i]){
// int j = e[i];
// if(d[j] > d[t] + w[i]){
// d[j] = d[t] + w[i];
// dnt[j] = dnt[t] + 1;
// if(dnt[j] > n) return true;
// if(!st[j]){
// st[j] = true;
// p.push(j);
// }
// }
// }
// }
// return false;
// }
// signed main()
// {
// #ifdef ABC
// freopen("D:\\daily_Coding\\VScode-C&C++-Coding\\in.in", "r", stdin);
// freopen("D:\\daily_Coding\\VScode-C&C++-Coding\\out.out", "w", stdout);
// #endif
// ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
// memset(h,-1,sizeof h);//初始化头节点为-1
// cin>>n>>m;
// while (m--)
// {
// int a,b,c;
// cin>>a>>b>>c;
// add(a,b,c);
// }
// if(spfa()) cout<<"Yes"<<endl;
// else cout<<"No"<<endl;
// return 0;
// }
九、Floyd
9.1、Floyd求最短路
// /*
// 九、Floyd
// */
// //9.1、Floyd求最短路
// //https://www.acwing.com/problem/content/856/
// //854.Floyd求最短路
// /*
// 思路：三重循环，记住就好
// */
// #include<bits/stdc++.h>
// #define int long long
// #define endl '\n'
// #define x first
// #define y second
// #define INF 0x3f3f3f3f3f3f3f3f
// using namespace std;
// //using namespace __gnu_cxx;
// using ll = long long;
// typedef pair<int, int> PII;
// const int N = 210, M = 20010;
// int n,m,k;
// int a[N][N];//a[i][j]表示点i到点j的最短路径
// void Floyd(){
// for(int k=1;k<=n;k++)
// for(int i = 1;i<=n;i++)
// for(int j=1;j<=n;j++)
// a[i][j] = min(a[i][j], a[i][k] + a[k][j]);
// }
// signed main()
// {
// #ifdef ABC
// freopen("D:\\daily_Coding\\VScode-C&C++-Coding\\in.in", "r", stdin);
// freopen("D:\\daily_Coding\\VScode-C&C++-Coding\\out.out", "w", stdout);
// #endif
// ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
// cin>>n>>m>>k;
// for(int i=1;i<=n;i++){
// for(int j=1;j<=n;j++){
// if(i==j) a[i][j] = 0;
// else a[i][j] = INF;
// }
// }
// while(m--){
// int x,y,z;
// cin>>x>>y>>z;
// a[x][y] = min(a[x][y], z);
// }
// Floyd();
// while (k--)
// {
// int x,y;
// cin>>x>>y;
// if(a[x][y] > INF/2) cout<<"impossible"<<endl;
// else cout<<a[x][y]<<endl;
// }
// return 0;
// }
十、Prim
10.1、Prim算法求最小生成树
// /*
// 十、Prim
// */
// // //10.1、Prim算法求最小生成树
// //https://www.acwing.com/problem/content/860/
// //858.Prim算法求最小生成树
// /*
// 思路：
// */
// #include<bits/stdc++.h>
// #define int long long
// #define endl '\n'
// #define x first
// #define y second
// #define INF 0x3f3f3f3f3f3f3f3f
// using namespace std;
// using namespace __gnu_cxx;
// using ll = long long;
// typedef pair<int, int> PII;
// signed main()
// {
// #ifdef ABC
// freopen("D:\\daily_Coding\\VScode-C&C++-Coding\\in.in", "r", stdin);
// freopen("D:\\daily_Coding\\VScode-C&C++-Coding\\out.out", "w", stdout);
// #endif
// ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
// LONG_LONG_MAX;
// return 0;
// }
十一、Kruskal
11.1、Kruskal算法求最小生成树
// /*
// 十一、Kruskal
// */
// //11.1、Kruskal算法求最小生成树
// //
十二、染色法判定二分图
12.1、染色法判定二分图
// /*
// 十二、染色法判定二分图
// */
// //12.1、染色法判定二分图
// //
// /*
// 十三、匈牙利算法
// */
// //13.1、二分图的最大匹配
// ////////////////////////////////////////////////////////////国赛部分/////////////////////////////////
