当前位置: 首页 > news >正文

搜索与图论(一)(深搜,广搜,树与图的存储遍历,拓扑排序)

一、DFS

往深里搜,搜到叶子结点那里,回溯,到可以继续到叶子结点深搜的位置。

1、回溯一定要恢复现场

2、定义一个与当前递归层数有关的终止条件(题目要求的东西)

3、每层都用循环判断是否存在可以dfs的路

输出数字组合

#include<bits/stdc++.h>
//842排列数字 按照字典序将n个数
using namespace std;
const int N=1e5+10;
int path[N];//记录走过的路径
int st[N];//用来记录某个元素是否被用过
int n;
void dfs(int u)
{//先判断是否已经得到一个答案if(u==n){for(int i=0;i<n;i++)cout<<path[i]<<" ";puts("");return;}for(int i=1;i<=n;i++){if(!st[i])//剪枝的过程找到可以构成dfs路径的方向{st[i]=true;path[u]=i;dfs(u+1);path[i]=0;//恢复现场st[i]=false;}}
}
int main()
{cin>>n;dfs(0);return 0;
}

全排列的思想解决n皇后问题,用三个bool数组描述限制条件,用二维char数组保存结果,在恢复现场的时候也要恢复g数组,因为后面的其他结果可能不会将其覆盖掉。

#include<bits/stdc++.h>
//843 n皇后问题(全排列问题)
using namespace std;
const int N=20;
int path[N];//记录走过的路径
char g[N][N];
bool col[N],row[N],dg[N],udg[N];
int n;
void dfs(int u)
{//先判断是否已经得到一个答案if(u==n){for(int i=0;i<n;i++)puts(g[i]);puts("");return;}for(int i=0;i<n;i++){if(!col[i]&&!dg[u+i]&&!udg[n-u+i]){g[u][i]='Q';col[i]=dg[u+i]=udg[n-u+i]=true;dfs(u+1);col[i]=dg[u+i]=udg[n-u+i]=false;g[u][i]='.';}}
}
int main()
{cin>>n;for(int i=0;i<n;i++)for(int j=0;j<n;j++)g[i][j]='.';dfs(0);return 0;
}

 按照元素枚举的方式解决n皇后问题

#include<bits/stdc++.h>
//843 n皇后问题(全排列问题)
using namespace std;
const int N=20;
int path[N];//记录走过的路径
char g[N][N];
bool col[N],row[N],dg[N],udg[N];
int n;
void dfs(int x,int y,int u)//x为行,y为列
{if(y==n)y=0,x++;if(x==n){if(u==n)//有可能到头了也没有找到全部的皇后{for(int i=0; i<n; i++)puts(g[i]);puts("");}return;}//为什么要添加xy两个参数//因为这个思路不是循环式地剪枝,是利用递归进行搜索//处理坐标//不放当前位置dfs(x,y+1,u);//放当前位置if(!row[x]&&!col[y]&&!dg[x+y]&&!udg[n-y+x]){g[x][y]='Q';row[x]=col[y]=dg[x+y]=udg[n-y+x]=true;dfs(x,y+1,u+1);g[x][y]='.';row[x]=col[y]=dg[x+y]=udg[n-y+x]=false;}}
int main()
{cin>>n;for(int i=0; i<n; i++)for(int j=0; j<n; j++)g[i][j]='.';dfs(0,0,0);return 0;
}

二、BFS

一层一层地搜索,如果边都是1,bfs第一次搜到的点具有最短路性质

1、具有最短路性质的原因:因为bfs每次都向外扩展一层,依次找到距离起点为1,2,3的所有点。

#include<bits/stdc++.h>
//844走迷宫//添加路径
using namespace std;
const int N=110;
typedef pair<int,int>PII;
int g[N][N];//存图
int d[N][N];//存距离
PII q[N*N];//模拟队列
PII pre[N][N];//路径的前驱
//由于最短路性质,可以直接将当前节点前的一个结点作为前驱
int n,m;void bfs()
{memset(d,-1,sizeof d);//用于判断是否是第一次访问到//一个点可以有多个路径到达,但是第一个到达的一定是最短路d[0][0]=0;int hh=0,tt=0;q[0]={0,0};int dx[4]={-1,0,1,0},dy[4]={0,-1,0,1};while(hh<=tt)//只要非空{auto t=q[hh++];for(int i=0;i<4;i++){int x=t.first+dx[i],y=t.second+dy[i];if(x>=0&&x<n&&y>=0&&y<m&&g[x][y]==0&&d[x][y]==-1){d[x][y]=d[t.first][t.second]+1;q[++tt]={x,y};pre[x][y]=t;}}}int x=n-1,y=m-1;while(x||y){cout<<x<<" "<<y<<endl;x=pre[x][y].first;y=pre[x][y].second;}
}int main()
{cin>>n>>m;for(int i=0; i<n; i++)for(int j=0; j<m; j++)cin>>g[i][j];bfs();cout<<d[n-1][m-1];return 0;
}

三、邻接表邻接矩阵存图

1、邻接表的存法

2、使用h数组作为槽,利用e和ne数组和idx构造单链表存槽中相应结点有边相连的节点、

根据题意利用从1深搜,每一层用res存最大的子图的点数,每次计算出一个子连通图添加到sum中。

#include<bits/stdc++.h>
//846 树重心
using namespace std;
const int N=1e5+10,M=N*2;
typedef pair<int,int>PII;
int h[N],e[M],ne[M],idx;
bool st[N];
//h保存n个头结点
//在用数组模拟链表时,e保存链表结点值,ne保存边
//idx让这一切有序
int ans=N,n;//存结果
int dfs(int u)//u是结点的名字不是idx性质的
{st[u]=true;//标记这个结点已经被搜索过了//在遍历当前节点的所有子树之前int sum=1;//存所有子树的节点个数int res=0;//记录各个连通子图的节点个数for(int i=h[u];i!=-1;i=ne[i]){int j =e[i];if(st[j]==false)//只要这个结点的子树还没计算{int t=dfs(j);res=max(res,t);//存最大连通子图sum+=t;//所有子树}}res=max(res,n-sum);ans=min(ans,res);//保存最小的最大连通子图return sum;}void add(int a,int b)//头插法
{e[idx]=b;//每个idx都代表一个链表上的节点ne[idx]=h[a];h[a]=idx++;
}int main()
{memset(h,-1,sizeof h);//memset(st,false,sizeof st);//所有结点的单链表指向的位置都为空cin>>n;for(int i=0;i<n-1;i++){int a,b;cin>>a>>b;add(a,b),add(b,a);}dfs(1);cout<<ans<<endl;}

3、邻接表利用bfs计算最短路

#include<bits/stdc++.h>
//847图中点的层次
using namespace std;
const int N=1e5+10,M=2*N;
int n,m;
int h[N],e[N],ne[N],idx;
int d[N],q[N];
void add(int a,int b)
{e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}
int bfs()
{int hh=0,tt=0;memset(d,-1,sizeof d);q[0]=1;//1是结点的名字,入队d[1]=0;//到第一个结点的距离为0//数组模拟队列的时候hh永远指向队列的第一个元素,tt永远指向队尾,所以判断队列不为空的判断条件是hh<=tt。while(hh<=tt){int t=q[hh++];//拿出队头元素for(int i=h[t];i!=-1;i=ne[i])//遍历与其相连的所有边{int j=e[i];//if(d[j]==-1){d[j]=d[t]+1;q[++tt]=j;}}}return d[n];
}
int main()
{cin>>n>>m;memset(h,-1,sizeof h);for(int i=0;i<m;i++){int a,b;cin>>a>>b;add(a,b);}cout<<bfs()<<endl;return 0;
}

4、有向无环图一定有拓扑序列,拓扑排序的实现

#include<bits/stdc++.h>
//848拓扑排序
using namespace std;
const int N=1e5+10,M=2*N;
int n,m;
int h[N],e[N],ne[N],idx;
int d[N],q[N];void add(int a,int b)
{e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}bool topsort()
{int hh=0,tt=-1;for(int i=1;i<=n;i++){if(!d[i])q[++tt]=i;}while(hh<=tt){int t=q[hh++];for(int i=h[t];i!=-1;i=ne[i]){int j=e[i];d[j]--;if(!d[j])q[++tt]=j;}}return tt==n-1;
}int main()
{cin>>n>>m;memset(h,-1,sizeof h);for(int i=0;i<m;i++){int a,b;cin>>a>>b;add(a,b);d[b]++;}if(!topsort())puts("-1");else{for(int i=0;i<n;i++)cout<<q[i]<<" ";puts("");}
}

相关文章:

搜索与图论(一)(深搜,广搜,树与图的存储遍历,拓扑排序)

一、DFS 往深里搜&#xff0c;搜到叶子结点那里&#xff0c;回溯&#xff0c;到可以继续到叶子结点深搜的位置。 1、回溯一定要恢复现场 2、定义一个与当前递归层数有关的终止条件&#xff08;题目要求的东西&#xff09; 3、每层都用循环判断是否存在可以dfs的路 输出数字…...

【开源】基于JAVA+Vue+SpringBoot的停车场收费系统

目录 一、摘要1.1 项目介绍1.2 项目录屏 二、功能模块2.1 停车位模块2.2 车辆模块2.3 停车收费模块2.4 IC卡模块2.5 IC卡挂失模块 三、系统设计3.1 用例设计3.2 数据库设计3.2.1 停车场表3.2.2 车辆表3.2.3 停车收费表3.2.4 IC 卡表3.2.5 IC 卡挂失表 四、系统实现五、核心代码…...

DDoS攻击激增,分享高效可靠的DDoS防御方案

当下DDoS攻击规模不断突破上限&#xff0c;形成了 "网络威胁格局中令人不安的趋势"。专业数据显示&#xff0c;对比2022年上半年与2023年上半年&#xff0c;所有行业的DDoS攻击频率增加了314%。其中零售、电信和媒体公司遭受的攻击规模最大&#xff0c;三个垂直行业的…...

打卡今天学习的命令 (linux

1.1 cp - 复制文件或目录 cp source destination cp -r source_directory destination # 递归复制目录及其内容1.2 rm - 删除文件或目录 rm file rm -r directory # 递归删除目录及其内容1.3 mv - 移动/重命名文件或目录 mv source destination mv old_name new_name # 重…...

[C#]无法获取源 https://api.nuge t.org/v3-index存储签名信息解决方法

参考网上大部分方法错误&#xff0c;根本不起作用。正确方法是 C:\Users\你的用户名\AppData\Roaming\NuGet找到NuGet.Config打开&#xff0c;看到类似下面信息&#xff08;可能不一样&#xff09; <?xml version"1.0" encoding"utf-8"?> <co…...

FRP内网穿透如何避免SSH暴力破解(二)——指定地区允许访问

背景 上篇文章说到&#xff0c;出现了试图反复通过FRP的隧道&#xff0c;建立外网端口到内网服务器TCP链路的机器人&#xff0c;同时试图暴力破解ssh。这些连接造成了流量的浪费和不必要的通信开销。考虑到服务器使用者主要分布在A、B、C地区和国家&#xff0c;我打算对上一篇…...

Unity类银河恶魔城学习记录4-1,4-2 Attack Logic,Collider‘s collision excepetion源代码 P54 p55

Alex教程每一P的教程原代码加上我自己的理解初步理解写的注释&#xff0c;可供学习Alex教程的人参考 此代码仅为较上一P有所改变的代码【Unity教程】从0编程制作类银河恶魔城游戏_哔哩哔哩_bilibili Entity.cs using System.Collections; using System.Collections.Generic; u…...

各种编程语言送祝福:2024龙年大吉

我是码农一枚&#xff0c;在这里用不同编程语言中祝福大家"2024&#xff0c;龙年大吉"~ Python print("2024&#xff0c;龙年大吉")Java public class Main {public static void main(String[] args) {System.out.println("2024&#xff0c;龙年大…...

C++中用Boost::Python调用Python模块

这个过程有挺多坑&#xff0c;记录一下。我这里的环境&#xff1a; Windows 11 Qt 6.2 Boost 1.8.4 CMake 3.25.2 Visual Stutio 2019&#xff08;主要用于C编译&#xff09; 1、下载并将Boost编译为静态库 b2.exe toolsetmsvc-14.2 install --prefixboost安装路径 links…...

MySQL查询缓存

MySQL查询缓存 MySQL在查询的时候首先会查询缓存&#xff0c;如果缓存命中的话就直接返回结果&#xff0c;不需要解析sql语句&#xff0c;也不会生成执行计划&#xff0c;更不会执行&#xff1b;如果没有命中缓存&#xff0c;则再进行SQL解析以及进行查询&#xff0c;并将结果返…...

Filter 实现过滤符合条件的请求并落库

其他系列文章导航 Java基础合集数据结构与算法合集 设计模式合集 多线程合集 分布式合集 ES合集 文章目录 其他系列文章导航 文章目录 前言 一、配置过滤器类 二、定义数据表、实体类、Mapper 2.1 DDL 2.2 实体类 2.3 Mapper 三、创建一个过滤器 四、实现 Nacos 配置…...

使用ChatGpt和文心一言辅助文章创作

近期在写数字水浒系列文章&#xff0c;使用了ChatGpt和文心一言进行辅助创作&#xff0c;整体感受不错&#xff0c;提高了工作效率。 在使用过程中&#xff0c;感觉文心的中文能力更强一些&#xff0c;主要体现在&#xff1a; 1 语料库更大&#xff0c;比如对水浒传了解的更多…...

OpenCV识别视频中物体运动并截取保存

功能很简单&#xff1a;输入原始视频&#xff0c;输出视频中有画面变化的部分 适合理解基本框架&#xff0c;可以在这个基础上增加各种酷炫时髦的功能 [doge] ※注释非常保姆级※ import cv2 import numpy as np import os from datetime import datetime# 检测两帧之间变化…...

6.Swift字面量

Swift 字面量 在 Swift 中&#xff0c;字面量是指直接指定数值、字符串、布尔值等常量的值的表示方式。使用字面量可以直接在代码中指定常量的值&#xff0c;而不需要通过变量或常量来存储。Swift 支持多种类型的字面量&#xff0c;包括整数、浮点数、布尔值、字符串、数组、字…...

拿捏循环链表

目录&#xff1a; 一&#xff1a;单链表&#xff08;不带头单向不循环&#xff09;与循环链表&#xff08;带头双向循环&#xff09;区别 二&#xff1a;循环链表初始化 三&#xff1a;循环链表头插 四&#xff1a;循环链表尾插 五&#xff1a;循环链表头删 六&#xff1…...

UMLChina公众号精选(20240207更新)

UMLChina服务 如何选择UMLChina服务 《软件方法》分步改进指南 做对《软件方法》强化自测题获得“软件方法建模师”称号 建模示范视频 [EA-029/石油钻井管理平台]35套UML/SysMLEA/StarUML的建模示范视频-全程字幕 UMLChina连EA经销商都不是&#xff0c;EA水平靠谱嘛&#xff1f…...

东南亚手游市场攻略:出海前的关键准备与注意事项

随着全球游戏市场的日益繁荣&#xff0c;越来越多的手游企业开始将目光投向海外市场&#xff0c;其中东南亚地区因其庞大的用户基数和逐渐成熟的游戏市场环境&#xff0c;成为了不少企业的首选目标。然而&#xff0c;想要在东南亚市场取得成功&#xff0c;并非易事。本文Nox聚星…...

python二维数组初始化的一个极其隐蔽的bug(浅拷贝)

初始化一个三行三列的矩阵 m n 3初始化方式1 a [[0 for i in range(m)] for j in range(n)]初始化方式2 b [] row [0 for i in range(0,m)] for i in range(0,n):b.append(row)分别输出两个初始化的结果 for row in a:print(row) for row in b:print(row)当前的输出为…...

iOS 需求 多语言(国际化)App开发 源码

一直觉得自己写的不是技术&#xff0c;而是情怀&#xff0c;一个个的教程是自己这一路走来的痕迹。靠专业技能的成功是最具可复制性的&#xff0c;希望我的这条路能让你们少走弯路&#xff0c;希望我能帮你们抹去知识的蒙尘&#xff0c;希望我能帮你们理清知识的脉络&#xff0…...

YOLOv8改进 | 利用训练好权重文件计算YOLOv8的FPS、推理每张图片的平均时间(科研必备)

一、本文介绍 本文给大家带来的改进机制是利用我们训练好的权重文件计算FPS,同时打印每张图片所利用的平均时间,模型大小(以MB为单位),同时支持batch_size功能的选择,对于轻量化模型的读者来说,本文的内容对你一定有帮助,可以清晰帮你展示出模型速度性能的提升以及轻量…...

Python|GIF 解析与构建(5):手搓截屏和帧率控制

目录 Python&#xff5c;GIF 解析与构建&#xff08;5&#xff09;&#xff1a;手搓截屏和帧率控制 一、引言 二、技术实现&#xff1a;手搓截屏模块 2.1 核心原理 2.2 代码解析&#xff1a;ScreenshotData类 2.2.1 截图函数&#xff1a;capture_screen 三、技术实现&…...

黑马Mybatis

Mybatis 表现层&#xff1a;页面展示 业务层&#xff1a;逻辑处理 持久层&#xff1a;持久数据化保存 在这里插入图片描述 Mybatis快速入门 ![在这里插入图片描述](https://i-blog.csdnimg.cn/direct/6501c2109c4442118ceb6014725e48e4.png //logback.xml <?xml ver…...

Nginx server_name 配置说明

Nginx 是一个高性能的反向代理和负载均衡服务器&#xff0c;其核心配置之一是 server 块中的 server_name 指令。server_name 决定了 Nginx 如何根据客户端请求的 Host 头匹配对应的虚拟主机&#xff08;Virtual Host&#xff09;。 1. 简介 Nginx 使用 server_name 指令来确定…...

BCS 2025|百度副总裁陈洋:智能体在安全领域的应用实践

6月5日&#xff0c;2025全球数字经济大会数字安全主论坛暨北京网络安全大会在国家会议中心隆重开幕。百度副总裁陈洋受邀出席&#xff0c;并作《智能体在安全领域的应用实践》主题演讲&#xff0c;分享了在智能体在安全领域的突破性实践。他指出&#xff0c;百度通过将安全能力…...

UR 协作机器人「三剑客」:精密轻量担当(UR7e)、全能协作主力(UR12e)、重型任务专家(UR15)

UR协作机器人正以其卓越性能在现代制造业自动化中扮演重要角色。UR7e、UR12e和UR15通过创新技术和精准设计满足了不同行业的多样化需求。其中&#xff0c;UR15以其速度、精度及人工智能准备能力成为自动化领域的重要突破。UR7e和UR12e则在负载规格和市场定位上不断优化&#xf…...

代理篇12|深入理解 Vite中的Proxy接口代理配置

在前端开发中,常常会遇到 跨域请求接口 的情况。为了解决这个问题,Vite 和 Webpack 都提供了 proxy 代理功能,用于将本地开发请求转发到后端服务器。 什么是代理(proxy)? 代理是在开发过程中,前端项目通过开发服务器,将指定的请求“转发”到真实的后端服务器,从而绕…...

C++:多态机制详解

目录 一. 多态的概念 1.静态多态&#xff08;编译时多态&#xff09; 二.动态多态的定义及实现 1.多态的构成条件 2.虚函数 3.虚函数的重写/覆盖 4.虚函数重写的一些其他问题 1&#xff09;.协变 2&#xff09;.析构函数的重写 5.override 和 final关键字 1&#…...

MySQL 知识小结(一)

一、my.cnf配置详解 我们知道安装MySQL有两种方式来安装咱们的MySQL数据库&#xff0c;分别是二进制安装编译数据库或者使用三方yum来进行安装,第三方yum的安装相对于二进制压缩包的安装更快捷&#xff0c;但是文件存放起来数据比较冗余&#xff0c;用二进制能够更好管理咱们M…...

深度学习水论文:mamba+图像增强

&#x1f9c0;当前视觉领域对高效长序列建模需求激增&#xff0c;对Mamba图像增强这方向的研究自然也逐渐火热。原因在于其高效长程建模&#xff0c;以及动态计算优势&#xff0c;在图像质量提升和细节恢复方面有难以替代的作用。 &#x1f9c0;因此短时间内&#xff0c;就有不…...

tomcat指定使用的jdk版本

说明 有时候需要对tomcat配置指定的jdk版本号&#xff0c;此时&#xff0c;我们可以通过以下方式进行配置 设置方式 找到tomcat的bin目录中的setclasspath.bat。如果是linux系统则是setclasspath.sh set JAVA_HOMEC:\Program Files\Java\jdk8 set JRE_HOMEC:\Program Files…...