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

PTA 哈密尔回路(建图搜索)

题目

著名的“汉密尔顿(Hamilton)回路问题”是要找一个能遍历图中所有顶点的简单回路(即每个顶点只访问 1 次)。本题就要求你判断任一给定的回路是否汉密尔顿回路。

输入格式:

首先第一行给出两个正整数:无向图中顶点数 N(2<N≤200)和边数 M。随后 M 行,每行给出一条边的两个端点,格式为“顶点1 顶点2”,其中顶点从 1 到N 编号。再下一行给出一个正整数 K,是待检验的回路的条数。随后 K 行,每行给出一条待检回路,格式为:

n V1 V2⋯ Vn

其中 n 是回路中的顶点数,Vi是路径上的顶点编号。

输出格式:

对每条待检回路,如果是汉密尔顿回路,就在一行中输出"YES",否则输出"NO"。

  • 输入样例:
6 10
6 2
3 4
1 5
2 5
3 1
4 1
1 6
6 3
1 2
4 5
6
7 5 1 4 3 6 2 5
6 5 1 4 3 6 2
9 6 2 1 6 3 4 5 2 6
4 1 2 5 1
7 6 1 3 4 5 2 6
7 6 1 2 5 4 3 1
  • 输出样例:
YES
NO
NO
NO
YES
NO

题解

#include <iostream>
#include <vector>
#include <cstring>
using namespace std;const int N = 210;
int n, m, idx = 0;
int h[N];
int e[N * N];
int ne[N * N];
bool mry[N];void add(int a, int b) {e[idx] = b;ne[idx] = h[a];h[a] = idx++;
}int main() {memset(h, -1, sizeof(h));cin >> n >> m;while (m--) {int x, y;cin >> x >> y;add(x, y);add(y, x);}int k;cin >> k;while (k--) {memset(mry, false, sizeof(mry));int num = 1;int kk, beg, end;cin >> kk ;int p[kk+1];for(int i=1;i<=kk;i++){cin >>p[i];}beg=p[1];end=p[kk];if (kk != n + 1 || beg != end) {cout << "NO" << endl;continue;}mry[beg] = true;int be = beg;for (int i = 2; i <= kk; i++) {int temp=p[i];if (mry[temp] && i != kk) {cout << "NO" << endl;break;}bool f = false;for (int j = h[be]; j != -1; j = ne[j]) {int l = e[j];if (l == temp) {f = true;break;}}if (!f) {cout << "NO" << endl;break;}mry[temp] = true;be = temp;num++;}bool flag2 = false;for (int i = 1; i <= n; i++) {if (!mry[i]) flag2 = true;}if (num == n + 1 && !flag2)cout << "YES" << endl;}return 0;
}

思路

建立静态链表,然后按照题目给的顺序遍历搜索即可。

相关文章:

PTA 哈密尔回路(建图搜索)

题目 著名的“汉密尔顿&#xff08;Hamilton&#xff09;回路问题”是要找一个能遍历图中所有顶点的简单回路&#xff08;即每个顶点只访问 1 次&#xff09;。本题就要求你判断任一给定的回路是否汉密尔顿回路。 输入格式&#xff1a; 首先第一行给出两个正整数&#xff1a…...

如何利用产品帮助中心提升用户体验

在当今竞争激烈的市场中&#xff0c;提供优秀的用户体验是吸引和保留客户的关键。而一个高效和易于使用的产品帮助中心&#xff0c;正成为越来越多企业用以提升用户体验的重要工具。产品帮助中心是一个集中的信息库&#xff0c;为用户提供关于产品功能、故障排除、常见问题解答…...

【Python大数据笔记_day05_Hive基础操作】

一.SQL,Hive和MapReduce的关系 用户在hive上编写sql语句,hive把sql语句转化为MapReduce程序去执行 二.Hive架构映射流程 用户接口: 包括CLI、JDBC/ODBC、WebGUI&#xff0c;CLI(command line interface&#xff09;为shell命令行&#xff1b;Hive中的Thrift服务器允许外部客户端…...

css呼吸效果实现

实现一个图片有规律的大小变化&#xff0c;呈现呼吸效果&#xff0c;怎么用CSS实现这个呼吸效果呢 一.实现 CSS实现动态效果可以使用动画( animation)来属性实现&#xff0c;放大缩小效果可以用transform: scale来实现&#xff0c;在这基础上有了动画&#xff0c;就可以设置一个…...

机器视觉opencv答题卡识别系统 计算机竞赛

0 前言 &#x1f525; 优质竞赛项目系列&#xff0c;今天要分享的是 &#x1f6a9; 答题卡识别系统 - opencv python 图像识别 该项目较为新颖&#xff0c;适合作为竞赛课题方向&#xff0c;学长非常推荐&#xff01; &#x1f947;学长这里给一个题目综合评分(每项满分5分…...

2024年的后端和Web开发趋势

目录 1 2 3 4 5 1 不断变化的数字创新格局可能让人感觉像是一场无情的竞赛。作为开发人员&#xff0c;你的痛苦是真实的——交付尖端产品、保持竞争力、跟上不断变化的用户期望&#xff0c;综合起来你的压力可能是压倒性的。 但是&#xff0c;如果我们告诉你有一个指南针…...

对比了10+网盘资源搜索工具,我最终选择了这款爆赞的阿里云盘、百度网盘、夸克网盘资源一站式搜索工具

盘友圈&#xff08;https://panyq.com&#xff09;是一个综合性的网盘搜索站&#xff0c;与其他网盘搜索工具相比&#xff0c;它具有多个独特的优点&#xff0c;使其成为用户们首选的平台。 首先&#xff0c;盘友圈汇集了阿里云盘、百度网盘和夸克网盘等主流网盘资源&#xff…...

GoLong的学习之路(二十)进阶,语法之反射(reflect包)

这个是为了接上之前的语法篇的。按照我的学习计划&#xff0c;这里此时应该有一个小项目来做一个统合。但是吧&#xff0c;突然觉得&#xff0c;似乎也没必要。能学go的大部分肯定都是有其他语言的基础的。 接下来说反射 文章目录 反射介绍reflect包TypeOftype name和type kin…...

关于表单校验,:rules=“loginRules“

在写好validator相关的方法后&#xff0c;rule测试没有生效 <el-form ref"loginForm" :model"loginForm" :rules"loginRules" class"login-form" <el-form-item prop"username"> <el-input ref"usernam…...

统一消息分发中心设计

背景 我们核心业务中订单完成时&#xff0c;需要完成后续的连带业务&#xff0c;扣件库存库存、增加积分、通知商家等。 如下图的架构&#xff1a; 这样设计出来导致我们的核心业务和其他业务耦合&#xff0c;每次新增连带业务或者去掉连带业务都需要修改核心业务。 一方面&…...

前端项目导入vue和element

1.安装nodejs 下载链接https://cdn.npmmirror.com/binaries/node/v18.18.0/node-v18.18.0-x64.msi 进入cmd 命令行模式 管理员身份运行 输入 &#xff08;node -v&#xff09;能看到版本号 npm config set prefix "C:\Program Files\nodejs" 默认路径 npm config…...

【11】使用透视投影建立一个3D空间的测试

核心操作&#xff1a; 1.proj view model 这三个矩阵 glm::mat4 mvp m_Proj * m_View * model; m_Shader->Bind(); m_Shader->SetUniformMat4f("u_MVP", mvp);着色器里面就&#xff1a; proj:投影矩阵&#xff0c;可以选择正交投影&#xff0c;或者透视投影…...

【广州华锐互动】VR影视制片虚拟仿真教学系统

随着虚拟现实(VR)技术的不断发展&#xff0c;VR在影视制片教学中的应用场景也变得越来越丰富。本文将介绍VR在影视制片教学中的常见应用场景及其意义&#xff0c;并通过案例分析来更好地展示其应用前景。 在影视制片教学中&#xff0c;VR可以提供一种沉浸式的制作体验。其中&am…...

从研发域到量产域的自动驾驶工具链探索与实践

导读 本文整理自 2023 年 9 月 5 日百度云智大会 - 智能汽车分论坛&#xff0c;百度智能云自动驾驶云研发高级经理徐鹏的主题演讲《从研发域到量产域的自动驾驶工具链探索与实践》。 全文中部段落附有演讲中 2 个产品演示视频的完整版&#xff0c;精彩不容错过。 (视频观看&…...

404. 左叶子之和

原题链接&#xff1a;404. 左叶子之和 思路&#xff1a; 首先要注意是判断左叶子&#xff0c;不是二叉树左侧节点&#xff0c;所以不要上来想着层序遍历。 节点A的左孩子不为空&#xff0c;且左孩子的左右孩子都为空&#xff08;说明是叶子节点&#xff09;&#xff0c;那么A节…...

基于SSM的课程管理系统

末尾获取源码 开发语言&#xff1a;Java Java开发工具&#xff1a;JDK1.8 后端框架&#xff1a;SSM 前端&#xff1a;Vue 数据库&#xff1a;MySQL5.7和Navicat管理工具结合 服务器&#xff1a;Tomcat8.5 开发软件&#xff1a;IDEA / Eclipse 是否Maven项目&#xff1a;是 目录…...

【hcie-cloud】【5】华为云Stack规划设计之华为云Stack标准化配置、缩略语【下】

文章目录 前言、华为云Stack交付综述为云Stack标准组网华为云Stack标准化配置华为云Stack配置概览华为云Stack云服务全视图华为云Stack部署方案节点类型说明华为云Stack云服务组件部署场景管理节点部署原则云平台管理规格华为云Stack IaaS场景&高阶场景起步必选部署组件x86…...

搭建自己的MQTT服务器,实现设备上云(Ubuntu+EMQX)

一、EMQX介绍 这篇文章教大家在ECS云服务器上部署EMQX,搭建自己私有的MQTT服务器,配置EMQX实现设备上云,设备数据转发,存储;服务器我采用的华为云的ECS服务器,系统选择Ubuntu系统。 Windows版本的看这里: https://blog.csdn.net/xiaolong1126626497/article/details/1…...

web3案例中解决交易所中 ETH与token都是0问题 并帮助确认展示是否成功

可能写了这么久 很多人会发现一个问 我们前面的案例 个人在交易所中的 自定义token 和 ETH 一直是放了个0 大家也不太敢确认是否真的有效 那么 很简单 我们操作 存入一些进交易所 不就ok了 我们 来看之前交易所写的代码 我们写了 depositEther 存入 ETH 和 depositToken 存入…...

unreal engine oculus 在vr场景中fade in , fade out

https://www.youtube.com/watch?vxRA7hRiXwuA...

挑战杯推荐项目

“人工智能”创意赛 - 智能艺术创作助手&#xff1a;借助大模型技术&#xff0c;开发能根据用户输入的主题、风格等要求&#xff0c;生成绘画、音乐、文学作品等多种形式艺术创作灵感或初稿的应用&#xff0c;帮助艺术家和创意爱好者激发创意、提高创作效率。 ​ - 个性化梦境…...

Java 语言特性(面试系列1)

一、面向对象编程 1. 封装&#xff08;Encapsulation&#xff09; 定义&#xff1a;将数据&#xff08;属性&#xff09;和操作数据的方法绑定在一起&#xff0c;通过访问控制符&#xff08;private、protected、public&#xff09;隐藏内部实现细节。示例&#xff1a; public …...

反向工程与模型迁移:打造未来商品详情API的可持续创新体系

在电商行业蓬勃发展的当下&#xff0c;商品详情API作为连接电商平台与开发者、商家及用户的关键纽带&#xff0c;其重要性日益凸显。传统商品详情API主要聚焦于商品基本信息&#xff08;如名称、价格、库存等&#xff09;的获取与展示&#xff0c;已难以满足市场对个性化、智能…...

AI Agent与Agentic AI:原理、应用、挑战与未来展望

文章目录 一、引言二、AI Agent与Agentic AI的兴起2.1 技术契机与生态成熟2.2 Agent的定义与特征2.3 Agent的发展历程 三、AI Agent的核心技术栈解密3.1 感知模块代码示例&#xff1a;使用Python和OpenCV进行图像识别 3.2 认知与决策模块代码示例&#xff1a;使用OpenAI GPT-3进…...

376. Wiggle Subsequence

376. Wiggle Subsequence 代码 class Solution { public:int wiggleMaxLength(vector<int>& nums) {int n nums.size();int res 1;int prediff 0;int curdiff 0;for(int i 0;i < n-1;i){curdiff nums[i1] - nums[i];if( (prediff > 0 && curdif…...

c#开发AI模型对话

AI模型 前面已经介绍了一般AI模型本地部署&#xff0c;直接调用现成的模型数据。这里主要讲述讲接口集成到我们自己的程序中使用方式。 微软提供了ML.NET来开发和使用AI模型&#xff0c;但是目前国内可能使用不多&#xff0c;至少实践例子很少看见。开发训练模型就不介绍了&am…...

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

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

算法岗面试经验分享-大模型篇

文章目录 A 基础语言模型A.1 TransformerA.2 Bert B 大语言模型结构B.1 GPTB.2 LLamaB.3 ChatGLMB.4 Qwen C 大语言模型微调C.1 Fine-tuningC.2 Adapter-tuningC.3 Prefix-tuningC.4 P-tuningC.5 LoRA A 基础语言模型 A.1 Transformer &#xff08;1&#xff09;资源 论文&a…...

NXP S32K146 T-Box 携手 SD NAND(贴片式TF卡):驱动汽车智能革新的黄金组合

在汽车智能化的汹涌浪潮中&#xff0c;车辆不再仅仅是传统的交通工具&#xff0c;而是逐步演变为高度智能的移动终端。这一转变的核心支撑&#xff0c;来自于车内关键技术的深度融合与协同创新。车载远程信息处理盒&#xff08;T-Box&#xff09;方案&#xff1a;NXP S32K146 与…...

springboot整合VUE之在线教育管理系统简介

可以学习到的技能 学会常用技术栈的使用 独立开发项目 学会前端的开发流程 学会后端的开发流程 学会数据库的设计 学会前后端接口调用方式 学会多模块之间的关联 学会数据的处理 适用人群 在校学生&#xff0c;小白用户&#xff0c;想学习知识的 有点基础&#xff0c;想要通过项…...